Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions

Sep 21, 2021 04:00 PM Singapore (Registration will open at 03:50 PM.)

Join Zoom Meeting:

Meeting ID: 958 7219 1837
Passcode: 4%Y.+Z2k


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:

About the Speaker

Vincent Y. F. Tan is currently a Dean’s Chair Associate Professor in the Department of Electrical and Computer Engineering (ECE) and the Department of Mathematics at the National University of Singapore (NUS). He received the B.A. and M.Eng. degrees in Electrical and Information Sciences from Cambridge University in 2005 and the Ph.D. degree in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology in 2011. His research interests include network information theory, machine learning, and statistical signal processing. He is currently an Editor of the IEEE Transactions on Signal Processing and the IEEE Transactions on Information Theory.

For more information about the ESD Seminar, please email