An Optimal Algorithm for Stochastic and Adversarial Bandits

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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 algorithm is based on online mirror descent with Tsallis entropy regularizer. We provide a complete characterization of such algorithms and show that Tsallis entropy with power α=1/2 achieves the goal. In addition, the proposed algorithm enjoys improved regret guarantees in two intermediate regimes: the moderately contaminated stochastic regime defined by Seldin and Slivkins (2014) and the stochastically constrained adversary studied by Wei and Luo (2018). 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 outperforms UCB1 and EXP3 in stochastic environments. In certain adversarial regimes the algorithm significantly outperforms UCB1 and Thompson Sampling, which exhibit almost linear regret.
Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS)
EditorsKamalika Chaudhuri, Masashi Sugiyama
PublisherPMLR
Publication date2019
Pages467-475
Publication statusPublished - 2019
Event22nd International Conference on Artificial Intelligence and Statistics (AISTAT) - Naha, Okinawa, Japan
Duration: 16 Apr 201918 Apr 2019

Conference

Conference22nd International Conference on Artificial Intelligence and Statistics (AISTAT)
LandJapan
ByNaha, Okinawa
Periode16/04/201918/04/2019
SeriesProceedings of Machine Learning Research
Volume89
ISSN1938-7228

ID: 225479605