Appendix 1 Proofs

Let B denote the batch size chosen for MABSplit. Note that there are at mostnB rounds in the main while loop (Line 6) of Algorithm 1 and hence at mostnmTB nmT confidence intervals computed across all arms and all steps of the algorithm. Since the mainwhile loop in the algorithm can only run nB times, the algorithm must terminate. Furthermore, if all confidence intervals throughout the algorithm are correct, itisimpossible for(f,t)tobe removed from the set ofcandidate arms. Finally, we consider the complexity of Algorithm 1. Letnused be the total number of arm pulls computed for each arm remaining in the set of candidate arms at a given point in the algorithm.