The reviewers consider the submission as relatively significant. The post-rebuttal discussion was mainly on whether Assumption 1 is not too limiting/strong/unnatural as the random selection of the arms comes after the nature selects the payoff distribution. Therefore while the current setting with Assumption 1 seems artificial, one reviewer suggested that a more natural setting would be to just consider deterministic a_i of the form a_i = i/N (and actually any fixed a_i as soon as there is a separation gap between each a_i). thought that the results could be easily extended to this case, without carefully checking this. The authors are also the requested to include the discussion on $p$. NOTE FROM PROGRAM CHAIRS: Broader Impact statements are required in all papers submitted to NeurIPS 2020. Although this work is largely theoretical, one reviewer notes: "Although the authors claim that the societal impact section is not applicable, the motivating example, in particular the allocation of scarce resources, does seem to raise potential ethical questions: how shall we allocate scarce resource such as ICU during for example the current COVID-19 pandemic is clearly something to be taken seriously. ...it may not be that appropriate to use such examples without further discussing the potential ethical concerns."