A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
Zicheng Hu, Cheng Chen
We investigate various stochastic bandit problems in the presence of adversarial corruption. A seminal work in this area is the BARBAR algorithm, which is both robust and efficient. However, it suffers from a regret of $O(KC)$, which does not match the lower bound $\Omega(C)$. In this paper, we first improve the BARBAR algorithm by proposing a novel framework called BARBAT, which eliminates the factor of $K$ to achieve an optimal regret bound up to a logarithmic factor. We also extend BARBAT to various settings, including multi-agent bandits, graph bandits, combinatorial semi-bandits and batched bandits. Compared to the Follow-The-Regularized-Leader (FTRL) framework, our methods offer the advantages of being parallelizable (making it suitable for multi-agent bandits and batched bandits) and having lower computational costs (especially in semi-bandits). Numerical experiments verifies the efficiency of proposed methods.