2025/02/11 by Zicheng Hu, Cheng Chen, Hu, Zicheng +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Blockchain Technology Applications and Security #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2502.07514
openalex publication_date 2025/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
We investigate various stochastic bandit problems in the presence of adversarial corruptions. A seminal work for this problem is the BARBAR~\citegupta2019better algorithm, which achieves both robustness and efficiency. However, it suffers from a regret of O(KC), which does not match the lower bound of Ω(C), where K denotes the number of arms and C denotes the corruption level. 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 with the Follow-the-Regularized-Leader framework, our methods are more amenable to parallelization, making them suitable for multi-agent and batched bandit settings, and they incur lower computational costs, particularly in semi-bandit problems. Numerical experiments verify the efficiency of the proposed methods.