the reviewers expressed their concern regarding the lack of experiments, we would like to stress that it is a theoretical

We would like to thank the reviewers for their comments and for their positive feedback on our contributions. The work of Kearns et al. (1999), which is very related to our setting, is also purely theoretical. Their work later inspired other algorithms that can be used in practice, such as UCT (Kocsis and Szepesvári, 2006). Nonetheless, to see the tightness of our guarantees, we had done the experiments described below. Using our MCTS analogy in Section 3.3, the two most computationally costly operations of SmoothCruiser are the (Lemma 2).