> Now I am a bit more clear on simple regret vs cumulative regret, but I think you should perhaps explain this with an example, maybe in the appendix
We can also add an example to the appendix. The use of MCTS in robotics would provide a good example, such as using MCTS for path planning [1,2]. If the robot is equipped with a simulated environment to search in, then simple regret is would be a more appropriate metric, and if the robot can only interact in the real world then cumulative regret would be a more appropriate metric.
[1] Janson, Lucas, Edward Schmerling, and Marco Pavone. "Monte Carlo motion planning for robot trajectory optimization under uncertainty." Robotics Research: Volume 2. Cham: Springer International Publishing, 2017. 343-361.
[2] Dam, Tuan, et al. "Monte-Carlo robot path planning." IEEE Robotics and Automation Letters 7.4 (2022): 11213-11220.
> Can you provide a proof sketch during the rebuttal so that I and other reviewers can verify the correctness?
Here are some proof sketches for the results in the paper. We've tried to keep them short so that they can feasibly be put into the papers in a similar form. But please let us know if any more details would be helpful.
### Theorem 5.2
Let $0<\pi_\min<\pi_\text{DENTS}(a|s)$ for all $s,a$, where $\pi_\min$ exists because $\exp(x)>0$ for any $x$ and $1/|\mathcal{A}|>0$ in Equation (21) (Lemma D.1). Then for a DENTS process $\Pr(E)\leq C_0\exp(-k_0N(s_t))$ iff $\Pr(E)\leq C_1\exp(-k_1N(s_t,a_t))$ iff $\Pr(E)\leq C_2\exp(-k_2N(s_{t+1}))$ holds for any event $E$ and constants $C_0,C_1,C_2,k_0,k_1,k_2$, which can be shown using $\pi_\min$ with Hoeffding bounds over indicator variables (Lemmas D.4, D.5).
We can then show $\Pr\left(\left|\hat{Q}^{N(s_1,a)}(s_1,a) - Q^*(s_1,a)\right| > \varepsilon \right)\leq C_3\exp(-k_3\varepsilon^2n)$ by induction, where the base case of the induction $\hat{V}^{N(s_{H+1})}(s_{H+1}) = V^*(s_{H+1}) = 0$ holds vacuously (Lemmas D.10, D.15 and Theorem D.16). Let $\Delta_\mathcal{M}$ be a small constant (Equation (105)) such that $\forall a\in\mathcal{A}. \left|\hat{Q}^{N(s_1,a)}(s_1,a) - Q^*(s_1,a)\right| \leq \Delta_\mathcal{M}/2 \implies \psi_\text{DENTS}(s_1)=\pi^*(s_1)$. Then setting $\varepsilon=\Delta_\mathcal{M}/2$ gives a bound on $\Pr(\psi_\text{DENTS}(s_1)\neq\pi^*(s_1))$ which can be used in the definition of simple regret to give the result.
### Theorem 5.1
Theorem 5.1 follows immediately from Theorem 5.2, as mathematically BTS is a special case of DENTS with $\beta(m)=0$.
### Theorem 4.2
$\Pr\left(\left|\hat{Q_{\text{sft}}}^{N(s_1,a)}(s_1,a) - {Q_{\text{sft}}}^*(s_1,a)\right| > \varepsilon \right)\leq C_4\exp(-k_4\varepsilon^2n)$ can be shown similarly to Theorem 5.2. The restriction on the value of $\alpha$ is required, as similar to Theorem 5.2, we need to use $\left(\alpha\leq \Delta_\mathcal{M}/3H\log |\mathcal{A}|\right) \land \left(\forall a\in\mathcal{A} \left|\hat{Q_{\text{sft}}}^{N(s_1,a)}(s_1,a) - {Q_{\text{sft}}}^*(s_1,a)\right| \leq \Delta_{\mathcal{M}}/3\right) \implies \psi_\text{MENTS}(s_1)=\pi^*(s_1)$ to bound the probability of $\psi_{\text{MENTS}}(s_1)\neq \pi^*(s_1)$.
### Proposition 4.1
This follows from computing the values of $Q^*_{\text{sft}}(1,a_1)$ and $Q^*_{\text{sft}}(1,a_2)$ in the modified 10-chain from Figure 1 of the paper using a temperature of $\alpha=1$. (Note that here $a_1,a_2$ refers to the two actions that can be taken in the D-Chain, rather than the variables representing the first and second actions taken on a trial. We will update the figure and paper to avoid this naming clash). We can use $\Pr\left(\left|\hat{Q_{\text{sft}}}^{N(s_1,a)}(s_1,a) - {Q_{\text{sft}}}^*(s_1,a)\right| > \varepsilon \right)\leq C_4\exp(-k_4\varepsilon^2n)$ from Theorem 4.2, to show $\Pr(\psi_\text{MENTS}(1) = a_1)\rightarrow 1$ as $n\rightarrow \infty$ below, so gives MENTS a simple regret that stays above 0 as $n$ tends to infinity.
N.B. Original response on 19/8, edited on 20/8.