Dear reviewer,

thank you for the detailed review and many great comments, questions and suggestions, and especially for the many on-point clarification questions which point out directly where our explanations are not clear and will help us significantly improve the presentation of the paper.

1. Thanks for pointing that out, we will make sure that the below is made clear and explicit in the paper. RND / counts are used to estimate the epistemic uncertainty in reward function and / or transition function locally for a transition $(s,a)$. As opposed to:

2. i. the uncertainy for $(S',a)$, where the state itself is uncertain (in Equation 7, for example), and ii. the uncertainty in value $\sigma_V(s_T)$, which must take into account uncertainty from future decisions and not just the novelty of $s_T$ locally. Which is why we refer to counts / RND as local measures of uncertainty, or measures of local uncertainty (local uncertainties).

3. The UBE prediction is used to approximate the uncertainty of value $U^\pi(s_T) \approx \sigma^2_V(s_T)$ at the leaves $s_T$. We mention this in section 3.3 in the second paragraph and we will make sure this is made more clear.

4. We refer to the epistemic uncertainty of backups $Var[\nu^i]$ during planning, where the $Var[\nu^i]$ will grow when the agent plans in untrained areas, and shrink when it plans in trained areas. Does that make sense? We will make sure it is made clear in the paper (or removed).

5. We bundle the epistemic uncertainty for reward and transition together into one score, which relates to the observation in 1., that they are both functions of the novelty of the transition locally. We propagate this score as if the transitions are certain, thus dropping the Jacobians' computation in practice. While this may seem crude, we believe it is reasonable in the deterministic-transition environments that E-MCTS is tailored for. If the epistemic uncertainty estimate is reliable, this allows us to give maximum uncertainty score to all trajectories that lead the agent into at least one unobserved transition, and a reasonable score through all observed transitions. We currently touch on this in Appendix D.4, but we will make sure we modify the presentation of the uncertainty propagation in the paper to include this discussion.

6. All updates in E-MCTS are local per node along the backup path $\nu^i$ of planning step $i$ (similar to MCTS). We will make sure this is clear in the paper and in the pseudocode.

7. We have not compared to standard MCTS, but only focused on turning the learning-based Alpha/MuZero into an epistemic algorithm, and showing benefits from that in the form of deep exploration. Prior to this question, we have not considered as part of the motivation for this work the advantage of learned value functions over rollouts, that rollouts-based MCTS cannot "learn" from one episode to the next, but Alpha/MuZero can, and thus epistemic Alpha/MuZero can explore an environment much more efficiently over time than MCTS. We believe that this is another setting where we can motivate the benefit of epistemic learning-based algorithms over non-epistemic, non-learning based planning algorithms. We hope to include results on more complex environments with the next iteration of the paper.

Does this address the reviewer's questions?

I thank the authors for their time and effort in addressing the issues I raised. I find the work interesting, and I believe that refining the paper's presentation and incorporating experiments that compare against MuZero on environments which doesn't require deep exploration could significantly enhance its overall quality.

Dear reviewer,

thank you for the detailed review and the great comments, notes and questions.

1. In our understanding, Alpha/MuZero are designed for and traditionally evaluated in deterministic environments where exploration may still be important (Atari hard exploration, Go, Chess), which we believe makes deterministic Deep Sea a suitable testbed for the hard-exploration deterministic-environment setting. Note that the lack of information sourced in unobserved transitions in enough by itself to introduce epistemic uncertainty which is important to take into account and propagate in the planning tree, even in the presence of entirely deterministic transitions and rewards. Since stochastic Deep Sea has stochastic transitions, we do not believe it is best suited to evaluate E-MCTS which we design on the framework of baseline Alpha/MuZero for a determinstic transition environments. On the other hand, stochastic-reward deterministic-transition Deep Sea (perhaps not the classic variation of the environment or a classic Alpha/MuZero setting, but also not an unreasonable one) can be used to evaluate E-MCTS' in the non-deterministic reward setting. We will make sure the above is discussed in the paper.

2. We believe this depends on the choice of transition-epistemic-uncertainty estimation mechanism. For example, if we choose 0 uncertainty for visited transitions and 1 for unvisited (suitable for a deterministic environment with bounded rewards), $\sigma_{q}(s,a)$ will be zero once all transitions in all trajectories evaluated from this node have been visited. However, if we choose $\sigma_r = \frac{1}{\epsilon + \sqrt{N}} > 0$ which is suitable for a reward function $r(s,a) \sim N(\mu(s,a), 1)$, the epistemic uncertainty $\sigma_r, \sigma_q$ will not shrink to exactly zero except in the limit of infinite visitations. In Figure 3 we demonstrate that with RND the uncertainty goes numerically to zero in practice.

Does this address the reviewer's questions?

Dear reviewer,

thank you for the detailed review and the excellent comments, questions and additional references.

1. The methods in W1 and EMCTS are designed to contend with different settings and different sources of uncertainty, in our understanding. E-MCTS addresses the case where the model used in MCTS is itself uncertain (i.e. there is uncertainty about the means of the transition, reward and value functions), while the methods in W1 address other cases (where the environment and thus the model is a POMDP or where the leaves in the tree have predictions with arbitrary variances but still true means with respect to the environment). We believe that is also E-MCTS's main advantage and source of novelty.

2. We are in the process of evaluating EMCTS in two player zero-sum games but were not able to provide results within the timeframe of this rebuttal.

3. We first note that Figure 2 contains evaluation episodes' regret, not training episodes' regret. We will make sure this is clear in the paper. Due to the off policy training of the agents with Reanalyze and the properties of Deep Sea, the agents learn to solve the problem essentially immediately upon first interaction with the goal. As a result, the task becomes exclusively a "find the goal" task, and if the agents' off-policy training is stable no training episode will influence the evaluated regret after finding the goal for the first time.

Does this address the reviewer's questions?

Dear reviewer,

thank you for the detailed review and the excellent comments and questions.

1. Figure 2: left compares different agents across domains, from 10 by 10 to 50 by 50 (Deep Sea size), while Figure 2: right is just 30 by 30. We deemed the reduction of the standard deviation in the left figure as more important than the right, where our objective was to support the hypothesis that from a certain value of $\beta$ onward, a large range of values were sufficient. We note that each point in Figure 2: right is composed of 3 seeds, for a total of 24 independent seeds in the figure.

2. In the simple case where exploration is actually detrimental to learning, $\beta$ could simply be turned to zero of course. If the value and uncertainty are tuned between 0,1 (reasonable in Alpha/MuZero), and in challenging domains where exploration might be benefited from but it's not clear what is the correct exploration-exploitation tradeoff (for example Chess or Go), we believe that an exploration schedule that runs multiple episodes in parallel (or alternating) with different values of $\beta$ (let's say, one large one small), in addition to random exploration episodes as well as deterministic exploitation episodes that rely on policy / value churn for exploration, will result in a very strong exploration heuristic, although in the paper we only evaluated the very edge of this idea by alternating E-MCTS exploration and deterministic exploitation episodes. It is of course also possible to use a decay schdule for $\beta$, although we believe in many environments the natural decay of uncertainty might be sufficient.