Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds

Abstract

This paper considers the multi-armed bandit (MAB) problem and provides a new best-of-both-worlds (BOBW) algorithm that works nearly optimally in both stochastic and adversarial settings. In stochastic settings, some existing BOBW algorithms achieve tight gap-dependent regret bounds of $O({\sum }_{i:{\Delta }_i>0}\frac{\log T}{{\Delta }_i})$ for suboptimality gap ${\Delta }_i$ of arm $i$ and time horizon $T$. As Audibert et al. [2007] have shown, however, that the performance can be improved in stochastic environments with low-variance arms. In fact, they have provided a stochastic MAB algorithm with gap-variance-dependent regret bounds of $O({\sum }_{i:{\Delta }_i>0}(\frac{{\sigma }_i^2}{{\Delta }_i}+1)\log T)$ for loss variance ${\sigma }_i^2$ of arm $i$. In this paper, we propose the first BOBW algorithm with gap-variance-dependent bounds, showing that the variance information can be used even in the possibly adversarial environment. Further, the leading constant factor in our gap-variance dependent bound is only (almost) twice the value for the lower bound. Additionally, the proposed algorithm enjoys multiple data-dependent regret bounds in adversarial settings and works well in stochastic settings with adversarial corruptions. The proposed algorithm is based on the follow-the-regularized-leader method and employs adaptive learning rates that depend on the empirical prediction error of the loss, which leads to gap-variance-dependent regret bounds reflecting the variance of the arms.

Accepted for presentation at the 35th Annual Conference on Learning Theory (COLT 2022). Only the extended abstract will appear in the conference proceedings

Cited by in corpus (1)

• Best-of-Both-Worlds Algorithms for Partial Monitoring