Minimax

We thank reviewers for appreciating the originality of our work and providing constructive feedback. We address specific concerns below. Random selection in Alg. 1 means sampling uniformly The intuition behind Thm. 2 in explained But to interpret Thm. 2 alone: for any algorithm considered, if There is no missing factor of 2 in Eq.(28) and Eq.(26) Thm. 3 is as following: for any Pareto optimal rate Alg. 1 is thus Pareto optimal. Eq. after line 115 defines the hardness level of a given problem, Alg. 1 is different from the Distilled Note that we are also comparing to an algorithm, i.e., QRM2, that allows the reuse of statistics [12]. The lower bound in Section 2 is in the minimax sense, so it suffices to reduce to the single-best arm case.