Abstract
We consider a best arm identification (BAI) problem for stochastic banditswith adversarial corruptions in the fixed-budget setting of $T$ steps. Wedesign a novel randomized algorithm, Probabilistic Sequential Shrinking$(u)$(PSS$(u)$), which is agnostic to the amount of corruptions. When the amount ofcorruptions per step (CPS) is below a threshold, {PSS}$(u)$ identifies the bestarm or item with probability tending to $1$ as $T\rightarrow\infty$. Otherwise,the optimality gap of the identified item degrades gracefully with the CPS. Weargue that such a bifurcation is necessary. In addition, we show that when theCPS is sufficiently large, no algorithm can achieve a BAI probability tendingto $1$ as $T\rightarrow \infty$. In PSS$(u)$, the parameter $u$ serves tobalance between the optimality gap and success probability. En route, theinjection of randomization is shown to be essential to mitigate the impact ofcorruptions. Indeed, we show that PSS$(u)$ has a better performance than itsdeterministic analogue, the Successive Halving (SH) algorithm by Karnin et al.(2013). PSS$(2)$'s performance guarantee matches SH's when there is nocorruption. Finally, we identify a term in the exponent of the failureprobability of PSS$(u)$ that generalizes the common $H_2$ term for BAI underthe fixed-budget setting.