Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits

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.

References in corpus (9)

• The best of both worlds: stochastic and adversarial bandits
• More Adaptive Algorithms for Adversarial Bandits
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits
• Learning in Games: Robustness of Fast Convergence
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
• Reducing Dueling Bandits to Cardinal Bandits
• Fighting Bandits with a New Kind of Smoothness
• Connections Between Mirror Descent, Thompson Sampling and the Information Ratio

Cited by in corpus (6)

• Stochastic Linear Optimization with Adversarial Corruption
• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition
• Corralling Stochastic Bandit Algorithms
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives
• Accelerated learning from recommender systems using multi-armed bandit