Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
Abstract:
We consider a best arm identification (BAI) problem for stochastic bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a randomized algorithm, Probabilistic Sequential Shrinking(u) (PSS(u)). When the amount of corruption per step (CPS) is below a threshold, PSS(u) identifies the best arm with probability tending to 1 as T grows. Otherwise, the optimality gap of the identified item degrades gracefully with the CPS. We argue that such a bifurcation is necessary. The injection of randomization is shown to be essential to mitigate the impact of corruption. To demonstrate this, we design two attack strategies. We apply them to a deterministic analogue of PSS(u) known as Successive Halving (SH). The attack strategy results in a high failure probability for SH, but PSS(u) remains robust. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to 1 as T grows. The paper can be found at: http://proceedings.mlr.press/v139/zhong21a.html
Biodata:
Zixin Zhong is a research fellow at the department of Electrical and Computer Engineering (ECE). She graduated from the School of Mathematics in Sun Yat-sen University in 2017 and defended her PhD thesis in September of 2021. She is now working with Prof. Vincent Y. F. Tan from the ECE and Mathematics departments, as well as Prof. Wang Chi Cheung from the Industrial Systems Engineering and Management department (ISEM).
Zixin's research interests are in online machine learning and, in particular, multi-armed bandits. Her work has been presented at top machine learning (ML) conferences including ICML and AISTATS, and also in top ML journals such as the Journal of Machine Learning Research (JMLR).