Epistemic Monte Carlo Tree Search
Authors: Yaniv Oren
Viliam Vadocz
Matthijs T. J. Spaan
Wendelin Boehmer
Venue: ICLR 2025 Poster (2025)
Keywords: model based
epistemic uncertainty
exploration
planning
alphazero
muzero
Primary area: reinforcement learning
TL;DR: We extend A/MZ specifically and algorithms that use MCTS with learned models of value and / or dynamics in general to estimate and propagate epistemic uncertainty in search, and harness the search for deep exploration.

Abstract: The AlphaZero/MuZero (A/MZ) family of algorithms has achieved remarkable success across various challenging domains by integrating Monte Carlo Tree Search (MCTS) with learned models. Learned models introduce epistemic uncertainty, which is caused by learning from limited data and is useful for exploration in sparse reward environments. MCTS does not account for the propagation of this uncertainty however. To address this, we introduce Epistemic MCTS (EMCTS): a theoretically motivated approach to account for the epistemic uncertainty in search and harness the search for deep exploration. In the challenging sparse-reward task of writing code in the Assembly language SUBLEQ, AZ paired with our method achieves significantly higher sample efficiency over baseline AZ. Search with EMCTS 
solves variations of the commonly used hard-exploration benchmark Deep Sea - which baseline A/MZ are practically unable to solve - much faster than an otherwise equivalent method that does not use search for uncertainty estimation, demonstrating significant benefits from search for epistemic uncertainty estimation.

Published as a conference paper at ICLR 2025
EPISTEMIC MONTE CARLO TREE SEARCH
Yaniv Oren
Viliam Vadocz
Delft University of Technology 2628 CD Delft, The Netherlands y. oren@tudelft.nll
Delft University of Technology 2628 CD Delft, The Netherlands
Matthijs T. J. Spaan Delft University of Technology 2628 CD Delft, The Netherlands m.t.J t.j spaanStudelft.nl
Wendelin Böhmer
Delft University of Technology 2628 CD Delft, The Netherlands j w.w. wow.er@tudellf....
ABSTRACT
The AlphaZero/ Maanzeeer/MuZero MuZero (A/ MZ) family of algorithms has achieved remark- able success across various challenging domains by integrating Monte Carlo Tree Search (MCTS) with learned models. Learned models introduce epis- temic uncertainty, which is caused by learning from limited data and is useful for exploration in sparse reward environments. MCTS does not ac- count for the propagation of this uncertainty however. To address this, we introduce Epistemic MCTS (EMCTS): thcorctically motivated approach to account for the epistemic uncertainty in search and harness the search for deep exploration. In the challenging sparse-reward lask of writing code in the Assembly language SUBLEQ, AZ paired with our method achieves significantly higher sample efficiency over baseline AZ. Search with EMCTS solves variations of the commonly used hard-exploration benchmark Deep Sea - which baseline A/MZ are practically unable to solve - much faster than otherwise equivalent method that does not use search for uncertainty estimation, demonstrating significant benefits from search for epistemic uncertainty estimation.
INTRODUCTION
Many recent successes of reinforcement lcarning (RL) have been achieved by the model-based algorithm family of AlphaZero/ MuZero (A/MZ, Silver et al. 2018 Schrittwieser et al. 2020). A/MZ have out outperformet humans in games, in tasks that traditionally relied on intricale human engineering (Mandhane et al. 2022 and even made real world impact with the design of novel, more efficient algorithms (Fazii et al. 2022 Mankowitz et al. 2023) for day-to-day problems, task that is often formulated rewards are sparse, it is difficult to learn good policies without employing some form of deep exploration search for the rewards. Deep exploration refers the ability of the agent to direct itself towards novel transitions in the environment irrespective of how far away they are from the current state and promises up to exponential improvement in sample efficiency in sparse reward environments (Osband et al.) 2018
challenging sparse reward environment. When
At the core of A/MZ is the combination of Monte Carlo Tree Search (MCTS, (Swiechowski let al.) 2023) with learned models of value and/or or environment dynamics. Learned models introduce epistemic uncertainty, which refers to the uncertainty in the predictions of the model sourced in limited coverage of the state-action space during training (Hüllermeier & Waegeman 2021). Accounting for epistemic uncertainty allows the agent to discern between predictions that are based evidence (i.e. the learned predictor was trained on this input), or based on generalization (i.c. the learned predictor was not trained on this imput) and is useful for many purposes in online and offline RL. Common uses range from reducing overestimation errors through pessimism in the face of uncertainty (see Kumar et. al. 2020). to directing deep exploration through optimism in the face of uncertainly (see

---

Published as a conference paper at ICLR 2025
Neu & Pike- Burke 2020).
Harnessing search for exploration is popular approach in similar model based algorithms, such as Dreamer (Sekar et al. 2020).
MCTS, however, was designed for search with the true dynamics model and without value model, and as a result, does not account for epistemic uncertainty introduced from learning the models. For this reason, A/MZ cannot harness MCTS for deep exploration, nor benefit from the epistomic uncertainty associated with the predictions of the search tree in other ways. In this work we aim to address both, with three main contributions. Practical and theoretically motivated methods to (i) harness MCTS and epistemic uncertainty for coper-confidence-eee wea--bouddddeeee based deep exploration (Jin et al.) 2018) and (ii) propagate the epistemic uncertainty from learned models of value and/ or dynamics during search, which we call Epistemic MCTS (EMCTS). (iii) A parallelized implementation in JAX (Bradbury et al. 2018) of EMCTS paired with an AZ agent and an environment implementing the Assembly language SUBLEQ (Mazonka & Kolodin, 2011 We find that the propagation of epistemic uncertainty in EMCTS very similar to that of value in MCTS. As search with MCTS improves the value estimates at the root, we hypothesize that search with EMCTS similarly improves the epistemic uncertainty estimates at the root, resulting in accurate UCBs and more sample efficient exploration compared to a method that does not rely on search but is otherwise equivalent.
We evaluate EMCTS in the challenging, similar to real-world applications and sparse-reward task of programming in SUBLEQ, as well as in the commonly used hard-cxploration benchmark Deep Sea (Osband et al. 2020). Our method is able to find correct programs for a harder programming task in much smaller number of samples than the AZ baseline. In the Deep Sea benchmark, our method demonstrates deep exploration by solving stochastic and deterministic reward variations of the task, both of which baseline A A/MZ unable to solve in reasonable number of samples. In addition, EMCTS significantly outperforms an ablation that does not rely on search for epistemic uncertainty estimation but is otherwise equivalent, demonstrating significant advantages from search for uncertainty estimation.
2 BACKGROUND
In RL, an agent learns a behavior policy through interactions with an environment. The environment is represented by Markov Decision Process (MDP, [Bllman 1957) M AS. p, P,7), where S is a set of states, A set actions, P the initial state distribution, R : S A + R bounded possibly stochastic reward function, and P is transition distribution such that P(s'ss, a) specifies the probability of transitioning from state to state s' after exccuting action a. The objective Jn of the agent is to find policy (als), specifying the probability of selecting action a in state s, that maximizes the expected discounted return, also called value V", from the starting state distribution p:
H-1
J = E[V* somp =
7 (R(Rs, at) sompasy1 (oggsss-Pttsa))aaxx(a))))
(1)
The discount factor 7 is used in difinitehhoizzn MDPs, ie. = to guarantee
that the values remain bounded, and is commonly used in RL for training stability. A state-action Q-value function also often used: ("(ssa) EjR(s, a) + (V'('') s'mP(ss.)) We denote the value of the optimal policy x² with V*(s) = max, (s), Vs E. In offline RL, the agent must maximize this objective given a static dataset. In model-based RL (MBRL) the agent uses model of the dynamics of the environment (P, R) to optimize its policy, often through planning (Moerland et al. 2023 The dynamics are either learned al. 2020 provided (e.g.. in AZ, Silver el al. 2018 ). In Deep MBRL the agent utilizes deep neural networks (DNN, Goodlellow
from interactions (e.g., in MZ, Schrittwieser
el. al. 2016 to approximate any of the value, policy, reward and transition functions.
1 'Our implementation, inspired by 1 which is an open source game demonstrating SUBLEQ,, is available at hhttp://githh/ www//mcte.....oooooo alphazero
2

---

Published as a conference paper at ICLR 2025
2.1 MONTE CARLO TREE SEARCH
The MCTS algorithm constructs a tree with the current state & at its root to estimate the objective: arg m max, Q* (sr, a) (Browne et al. 2012), by iteratively performing selection,
expansion, simulation and backup. At each iteration of the algorithm a tra Lectory the tree is selected using tree search policy such UCT (Kocsis & Szepesvári 2006
x = UCT.(sE) = arg max q' (sk, a) + CUCT aEA
2 2log( "., ((ar.a))
(2)
[(s,,))
where (8k, a) denotes the number of times action a has been selected node 8k: Cuçr > 0 trades off exploration of new nodes in the tree with maximizing observed return and q' (5k, a) is the averaged return observed for this state action up to step i. Modern algorithms (such as A A/M use instead variations of PUCT (Rosin 2011
V., o (sL).(s)) arg max o' (sk: a) ((ass) CrUCT (+N(s acA
(3)
with some learned expanded with a value estimate v(st). MCTS propagates the return Dt of planning step i back along the planning trajectory {8). o3
т. When selection step arrives at a leaf si the node is
V'Ks ob Σ
(rr(sh+ kb) + 7 v(st), a) N a)
Σ w (sk. (4)
1=0
where abz = P/UCT:(s((+) and = [(kkt) akt)) for a deterministic transition func- tion ʃ: S and mean-reward function r(s, a) = E[R(s, a)]. In the original MCTS, the dynamics model m = (f.r) is provided to the agent and assumed to be correct for the true MDP M and the value estimate v(si)) is computed using Konte-Carlo (MC) rollouts with m. In AZ the value function (iilerr et al. 2018) and in MZ all functions f,r, are learned from interactions with the environment. and thus their predictions are uncertain outside of the training set. The prior-policy is trained with cross-entropy loss on targets extracted from the root of the tree. With Reanalyze (Schrittwieser et al., 2021), which uses search to generate fresh value and policy targets from off-policy data, A/MZ are able to learn off-policy.
2.2 QUANTIFYING UNCERTAINTY IN DEEP REINFORCEMENT LEARNING
Quantifying uncertainty in deep learning is active field of research (see Hüllermeier & Wacgeman 2021 Lockwood & Si 2022). In this work, we take the common approach for quantitying epistemic uncertainty as the variance in random variable that approzimates predictions that are consistent with dataset of observed interactions D. We model a learned function f, trained to approximate true function r on data D, f(s, a) & r(s, a), as a random variable with respect to the data: i(s, a) = R(ss a). We assume unbiased approximation E[A(s, := r(s; a), and use the variance V[R(s, a)] to quantify the epistemic uncertainty. In discrete state-action spaces, the epistemic uncertainty in reward or transition can be estimated as the novelty of a state or state-action pair using visitation counting. Exact counting, which is gemerally intractable in large state-action spaces, can be replaced by Hash-based counting (Tang et al. 2017), or methods that focus on direct estimation of the novelty of state-action pairs, such Random Network Distillation (RND, Burda et al, 2019).
In contrast, epistemic uncertainty a value prediction (+)( that is trained with TD-based targets, requires reasoning about uncertainty in the valuo-targets, as well as whether V was trained on at all. We follow the popular approach by [Steens (2000) of defining epistemic uncertainty in the value function as the variance of a Bayesian posterior of the Q-values of a
2 For notational simplicity we assume here a deterministic transition function f, so that nodes sky correspond to individual states. It is also possible to use stochastic transition model P, where nodes correspond to distributions of states, which are sampled by the selection step. The above equations remain the same, but the state corresponding $ is effectively random variable.
3

---

Published as a conference paper at ICLR 2025
policy conditioned on the data the agent has collected, as follows:
(s, a)] v [((saa) + Σ T(a'ls') P(s)s
(5)
Note that the epistemic uncertainty about rewards V[R] and transitions V[P] are induced by the data D the value function has been trained on, not by the agent's knowledge of the environment. Values predicted by Icarned value functions can thercfore be epistemically uncertain, even if a perfect model of the environment is known to the agent. In their work on the Uncertainty Bellman Equation (UBE), O O'Donoghue et al. (2018) propose to approximate an upper bound u" (&t, a+) 2 VIQ" (st, at)]- u" (8%, az) can be learned with (possibly n-step) TD targets in similar manner to value learning from local uncertainties a):
u" (st, a.) == (8 at) + + <a'' ((41)))))) u" (s)+1, S 17(ss, az) + +² max (S4x1"( (st+1, (6)
a'
The local uncertainty 77 can be derived from V[R] and V[P]. Note that the above incquality yields an upper bound on the epistemic uncertainty of any policy with training data D.
2.3 DEEP EXPLORATION WITH UPPER CONFIDENCE BOUNDS
A popular approach to harness epistemic uncertainty for deep exploration is that of optimism in the face of uncertainty (Lattimore & Szepesvari 2017), often formalized using an upper confidence bound (UCB) on the true value of the optimal policy (Azar et al. 2017 Jin et al. 2018 Acting greedily with respect to the maximum UCB guarantees exploration of the environment, The efficiency of UCB exploration depends on the epistemic uncertainty estimator. In environments with small statc-action spaces, epistemic uncertainty estimators that prediet maximum uncertainty for unvisited states can be used to guarantce exploration of every state-action pair. To explore continuous or large state-action domains in practical numbers of samples, using an UCB requires uncertainly estimalors that estimate the epistemic uncertainty in unvisited states s' based on similarity metric between s' and visited states E DD (Jin et al. 2023), such as imposed by RND, for example.
long as the UCB tightens with more samples from the environment.
3 DEEP EXPL.ORAIION WITH EPISTEMIC MCTS
To find optimal policy, an RL agent must explore the environment until all necessary information is gathered. When the agent uses search for action selection in the environment, it can search for exploration, exploitation,
trade-off between the two. When learned model vi is used in search, the agent faces a problem: the values gh in the search tree converge to Q the Q value in the learned model of the policy that is optimal in that model The In areas where the learned model is inaccurate, the search may lead to arbitrarily bad actions with respect to expected return in the true environment. From the perspective of exploration on the other hand, this presents an opportunity: by estimating the epistemic uncertainty the agent can identify the areas where the model is uncertain due to insufficient interactions, and use the uncertainty to direct exploration into these areas.
Our objective is then two-fold: To extend MCTS to estimate and propagate the epistemic uncertainty from the uncertain learned model and harness the epistemic uncertainty in the search to achieve deep exploration of the environment. To achieve this, we take the following steps: (i) Formulate the learned model nn random variable and use it to construct UCB on Q (Section 3.1. (ii) Propose search policies to track the maximum UCB exploration
objective (Section 3.2 (iii) Propagate the epistemic uncertainty through scarch, such that the epistemic uncertaitty V(g,, (s, a)] in nodes' value predictions dh (s. a) can be estimated
(Section 3.3 Search with learned transition models introduces additional challenges for
uncertainly propagation, which we address in Section 3.4
3.1 SEARCH WITH A LEARNED REWARD MODEL
For simplicity, we begin by formulating the problem of search with learned models only in terms of learned reward model and later extend the setup to learned value
4

---

Published as a conference paper at ICLR 2025
and transition models. Consider the following setting: the agent has access to dataset D = {(ss ag Tú, $t+1) S < N] transitions and rewards, as well as to the true (possibly stochastic) transition model P. The reward function is bounded with: max,, (R(s,a)] S Tmar- We define the uncertain model as a random variable M (P, It). The uncertain mean-reward function is defined a random variable ft in the standard manner for defining an epistemically uncertain model (see Section 2.2 such that c[](s,a)] r(s, a) the mean reward, and a( = [(=,a--))EL) E(s,,,r;) r R r(s, a), as the empirical mean of observed rewards. The epistemic uncertainty in reward prediction is defined as the variance V R(ss, a)]. We note that. R(s, a) is a bounded random variable over the interval [-Tmex, Tmar)) To facilitate constructing an upper confidence bound on Q" we define V[A(s.a) := mmans V(s, a) & D. That is, for unobserved transitions, the maximum variance possible for bounded random variable (Popoviciu 1935). The value with respect to the Markov chain induced by the random variable M then itself a random variable:
2 (s, ET.P
y'r a (st), 8:41 a.s,, a,),, = 5.00 = a). (7)
2=
where the expectation is with respect to π and P and not Å. Using this definition for the value in the model 2 is and its variance ViQ,, Nr ] construct upper confidence bound on Q' for deep exploration.
Theorem 1 For M, M, Q", 2% defined above and 8 E (0. 1]:
max ((0 & max (0% (8,
v8 / (V10% 2 1, v(s,a)
(8)
The proof is provided Appendix A.1 and relies on the linearity of Q in the reward function R. An extended UCB that is maintained in the presence of an uncertain transition model P is constructed in Appendix A.3 The UCB can be tracked by MCTS using epistemic search policics, which we propose next.
M
3.2 PLANNING FOR EXPLORATION WITH EPISTEMIC SEARCH
To harness search for deep exploration through the approximation of the UCB in Equation g propose Epistemic P P/UCT
changes are marked in blue):
QUUCT = arg max L (Sk, a) + Cucry 2 2log(E I,, N(s2.a))
(9)
((s..a)
oEA
VEn, (on,a))
@PPUCT
arg max aEA
2i (s6, + (a)>s)) CPUCT 1+N(ek.a)
(10)
where we define:
o (8k, N(
Σ
(s
Dr (Sk, a) +B N(s2.a) E
N(s
Vi 3u
[)),))]
(11)
1g (5).0)
Vag (#a,a))
The
3 2 can be tuned per task, or chosen to guarantee an upper confidence bound with specific confidence - 6, and v (sk, a) is defined in Equation 4 for specific model M. We suppress the dependence on planning step in the notation of 9 (5k. a) for simplicity. To maintain the property of PUCT, which assumes d is between Ó and 1 (Rosin 2011), one can use the Q normalization approach proposed by SShhitttiieerr et al. (0200) normalize the q scores. More modern variations of PUCT such as those proposed by Danihelka. et al. (2022) can be used by replacing Uú with of in the search objective. We note that in order to properly harness search policics that use a prior-policy for deep exploration, such EPUCT, the agent must learn
Te that is trained with an exploratory objective. Otherwise, the prior policy may direct the search away from the exploratory planning objective. To enable RUCUTT, in the following section
ppploration-prior--ee
5

---

Published as a conference paper at ICLR 2025
we propose methodology to estimate the epistemic uncertainty in backups and upper bound 1l a)).
3.3 PROPAGATING EPISTEMIC UNCERTAINTY IN SEARCH
To estimate Vgg a) we need to: (i) extend the problem setup to account for the learned value model, (ii) compute or upper bound the epistomic uncertainty in one backup VV (sk, a)] and (iii) compute or upper bound Vla (Sk, a)] using V ($k.a)].
Search with a Learned Value Model A learned value model V introduces an additional source of epistemic uncertainty into the search, V[V(s). In this case, for the UCB to hold
is important that the models M- = (f. R. are trained on the same data, which the popular choice in practice. This is sufficient to analytically maintain that V[V(s) 2 ViV 4 (s)] 5). To maintain this property in practice we choose the UBE (O'Donoghue eet. al. 2018 estimator û (see Section 2.2 and Equation 6 which upper bounds V[V(s) using MR(s a)]. To account for the possibility that ú is unreliable outside of the training set use the novelty of (s.a) to upper bound the uncertainty predicted by â (sec Appendix D.6 and Equation 25). When the reward model is not learned, such as in AZ, the value model still has epistemic uncertainty as it is trained from interactions and V[V(s) coincides with the definition of value uncertainty in model-free literature (Equation 5) This dcfinition accounts for uncertainty in transitions that are unobserved in the enviroument, regardless of whether the transitions are known to the planning model, capturing the uncertainty in value model that is trained from interactions. To estimate V[R(s,a)] RND and (pseudo-)counting methods can be used (see Section 2.2 for more detail).
(see Equation
Epistemic Uncertainty of the Backup The epistemic uncertainty in one backup step Viv M (5k, a)] starting at node sk and choosing action can be formulated as follows:
T-k-1
V (sk. 0)l
Σ 1=0
(iV + 2(T (V--))((((+))),
(12)
under the assumption that A( a) is independent from ((sk+j,a) a), Vi o j. and is independent from R conditional the data. We note that this assumption might be reasonable for some estimators (i.e., a table), but is not generally assumed to be true for DNNs. To avoid this assumption, we can instead upper bound the standard deviation of correlated backups using the sum of standard deviations (see Appendix A.2)
Epistemic Uncertainty of Node Values Since A/MZ use the same model M throughout planning, the returns predicted for different backups cannot be assumed be de-correlated. We propose to upper bound the epistemic uncertainty instead:
N(s..))
(N (((.
Vig a)] S ax (sk, a)
Σ ==
Vi a)]
(13)
where [ss,, a) is the number visitations to action a at node sy. We provide a complete derivation in Appendix A.2, Equation 13 completes the Epistemic MCTS (EMCTS) algorithm for learned value and/or or reward models. See Algorithm 1 for pscudo code of EMCTS with EUCT, where we suppress dependence on the model M for notation simplicity. Extensions to MCTS are marked in blue. In AZ, with a true reward model, EMCIS will use V[A(s,,)) a)] 0, V(s, a) E S x A, but still use v[V(s) 2 0.
To conclude this section we note that while in this work we motivate and later evaluate EMCTS from the perspective of deep exploration, EMCTS is not limited to this use case. Our method introduces to MCTS-basee estimate the epistemic uncertainty in the value predictions during and post search, which may be attractive for different purposes. Noted example are: (i) reducing over cstimation
algorithms such as A/MZ a novel capability to
errors with bound value targets of the form (s, - / (s.a)]. This approach is popular in model free AC methods implicitly (Fujimoto al. 2018 Haarnoja al. 2018
6

---

Published as a conference paper at ICLR 2025
Algorithm 1 EMCTS with EUCT. Requires f. o" and uncertainty estimators V(V), V[A]
1: function EMCTS((stat (9) D =0 for unmodified MCTS exploitation episodes
2: while within computation budget do
3: SELECT(s, ()
> traverses tree from root so and adds new leaf N(so.a)
4: return action drawn from ((oos) = En (s0.aa))
> MCTS action selection
5: function SELECT 8k, (3)
6: ag f arg a &² (sk, a) + CUCT 2 Togi and (a)
b Equation traverses tree adds new leaf
N [(x.0))
7: if ag already expanded then SELECT( ( ax),
8: else EXPAND(Sk: ax)
9:
function EXPAND(node sk. not yet expanded action as)
10:
Sk+1, (5k+1), R(( ax) + Execute MCTS expansion D creates a new leaf 8k+1
11:
Estimate epistemic variance of reward V [[ss,, ax.] and store in node 8k-1.
12:
Estimate epistemic variance of value VIV (sV())))) and store it in node 8k+1-
BACKUP(SE+1 (ss+1), (sk+1))) > updates the tree values & value variances
14:
function BACKUP(node sk+1, ret. (($++1, ax+1), ret. unc. V[p(sk+1, ax+1)l) 8k. ag, (5kk aR) f Execute MOTS backup step & updates g(sk; ax); N (ssk, as)
15:
16:
ViU(SK, ax) - V V[K(s ax) + " 4x-1)]
Equation 12
(5 ax) (sk: ax) + (x)
17:
Equation 13
((s..a))
18:
if then BACKUP(SE: (SKK ax), ((k)))))))
and explicitly (Ciosek et al. 2019), as well as in model-based RL (Zhou et al. 2020 and generally very common in offline RL (Kumar al. 2020 Ghasemipour
al. 2022).
This makes EMCTS an espeically attractive candidate to enhance A/ MZ's Reanalyze for al. 2021 We propose to track the objective O3r (s, a) - / V (s, a)] in search, i.c. to use EP EP/UCT but with 3 < (ii) Weighting value and policy losses by the estimate of the epistemic uncertainly in the value which was successful in online as well as oflline RL (Lee al. 2021 Wu al. 2021 The uncertainty of the value of the root of EMCTS can be used for this purpose.
offline-RI. or off-policy target generation (Schrittwieser
3.4 SEARCH WITH A LEARNED TRANSITION MODEL
Learned transition models introduce several challenges from the perspective EMCTS: (i) estimating epistemic uncertainty in the possibly-abstraceed planning space, (fi) propagating the uncertainty forward during search as future transitions become less cortain, addition to backwards, and (iii) propagating in such way that maintains the UCB constructed in Theorem 1 Multiple methods to overcome (i) have been successful in previous works, see Henaffi (2019): ; Sekar al. 2020).. In Appendix A.3 we propose an approach overcome (ii) and (ili) as well as discuss the challenges in more detail. In practice however, in Section we include experiments where a MZ agent fitted with a reliable uncertainty estimator for
V[R(s, a)] successfully demonstrates deep exploration without accounting for (ii) and (iii).
4 RELATED WORK
Search for exploration was used successfully in a number of previous works, see Jaksch al. (2010). Sun et al. (2011), Hester & Stone (2012). Shyam et al. 2019 Henaff (2019) Sekar et al. (2020), Lambert al. (2022) and Luis al. (2023). We add to this line of work EMCTS: designed for MCTS (and planning trees in general), practical and based in theory.
Tesauro et al. (2010) develop a Bayesian approach for aleatoric uncertainty propagation in MCTS. POMCP (Silver& & Veness 2010 POMCPOW (unberg & Kochenderler 2018 and BOMCP Mern et al. 2021) extend MCTS to POMDPs with a probabilistic Bayesian belief state at the nodes using a probabilistic model, while Stochastic MuZero (Antonoglou et al.,
2022) extends MuZero to the stochastic transitions setting by replacing the deterministic
Iransition function with Vector Quantised Variational AutoEncoder (van den Oord et al.
7

---

Published as a conference paper at ICLR 2025
2017 In these works, epistemic uncertainty is not distinguished used for exploration.
Latent disagreement ensembles [Lakshminarayanan et al. 2017
Ramesh et al. 2022 offer a
popular alternative to RND and counts. Wasserstein Temporal Ditterence (WTDD) Metelli
et al. 2019) offers an alternative to UBE (O O'Donoghue et al.
2018) for estimating value
uncertainty, using Wasserstein Barycenters (Agueh & Carlier 2011 to update a posterior
over Q functions in place of a standard Bayesian update. While UBE was criticized by Janz
et al. (2019) for being insufficient for deep exploration with posterior-sampllee based RL
(PSRL, Osband et al.) 2013), we note that the same shortcomings do not apply when UBE used for UCB-based exploration.
5 EXPERIMENTS
The task of writing code and finding new algorithms, where AZ has recently made world real-world impact (Fawzi et al., 2022 Mankowitz et al. 2023). is natural to formulate using sparse-reward environments where the actions of the agent are operations and reward is received when correct program is completed. Such environments represent hard exploration challenge: the state space is often exponential |A| in the actions A and the maximum length of the program L,, and while the number of possible solutions is generally unknown, it is in most cases very small compared to the number of possible sequences of operations. To evaluate the contribution of EMCTS in such real-world tasks we conduct experiments in the one-instruction Assembly programming language SUBLEQ (Section 5.1
To verify that EMCTS demonstrates deep exploration and benefits from search, we conduct experiments in the commonly used bard-exploration benchmark Deep Sea (Osband et al. 2020) (Section 5.2 Specifically, we are interested in the following:
RQT I Does EMCTS paired with an epislemic seurch policy demonstrule deep exploration with both AZ as well as MZ and in the presence of stochastic as well as determinislic rewards? RQ II Is there benefit in search with EMCTS for deep exploration, compared to an otherwise equivalent approach that does not use search, and if so, is the benefit retained in the presence of the learned transition model of MZ?
We also conduct an ablation study on the exploration parameter 33 to verify that the agent can learn stably from the possibly very-off-policy exploratory data provided by deep exploration.
5.1 SUBLEQ EXPERIMENTS
SUBLEQ is Turing-complete (excepting for finite memory) one-instruction programming language (Mazonka & Kolodin 2011). Because there is only one instruction, writing code in SUBLEQ summarizes to writing sequence of memory addresses. We model the action space with A = (O....,.' N - 1}, for N the size of the memory. The agent is rewarded with 1.0 when the sequence of addresses specifies program that solves the task, evaluated on a set of test cascs. The reward is otherwise zero. The observation space constitutes of an example input and corresponding desired output, the program written far, and the state of the input and output after executing the program on the example input. We limit the memory size to 16 and the maximum program length to 10 resulting in a state space of size < 16 se frillion unique states. We present results on two tasks: An easier task of outputting the negated input for positive inputs (Negate Positives), and a harder task of implementing the Identity Function. An implementation of Negate Positives in SUBLEQ of length 2 known, which means finding a solution without prior knowledge requires scarching on the order of 16² unique states. To the Identity Function an implementation of length 6 is known which suggests searching on the order of 166 as 16 million unique states. We provide more detailed introduction to SUBLEQ, description of the environment and the tasks in Appendix C The results are presented in Figure [
We compare two variations of EMCTS with AZ (E-AZ) to the AZ baseline. Both variations of E-AZ are able to solve the harder task in a much smaller number of samples than AZ. To estimate V[A( s')] one variation of E-AZ uses a hash based visit count that takes as input the complete state s', allowing the agent to, in principle, avoid searching the same state twice. The other E-AZ variation hashes only part of the state: the example input-output, before and after execution (IO hash), directing the agent to search actions that have
8

---

Published as a conference paper at ICLR 2025
Negate Rositives
Ideakity Function thand!
1.0
1.0-
bacoa Basatton Noum
0.8
0.6
0.6-
0.4
E-A2 30 Hash)
0.2
E-A2 80 Haght
0.2
E-A2 SMI Observa Hash)
E-AZ (Ru Observation Haeto
0.0
50000
150000
1.
1.2
Erieronment
Ervfrommntt stops
Figure 1: Sample efficiency. Left: the easy SUBLEQ Negate Posilines task. Right: the harder Identity Function task. Mean of seeds, two standard errors.
effect the output of the program. As expected from UCB-based method, E-AZ benefits from the more-appropriate uncertainty estimator and finds correct program much earlier with the 10 hash.
All agents use Danihelka et al. (2022)² i approach that combines Gumbel noise with Sequential Halving the root and modern variation of PUCT non-root nodes. For E-AZ variations, in online search (when selecting actions in the environment) the tree search policies use d (11) in place of 9 and an inlloaation-prioo-olliii *e (See Section 3.2). To select actions during evaluation,
well when generating largets with Reanalyze, the search uses EMCTS to propagale the uncertainly, but uses the exploitation prior policy a and Ogz in the search objective, in the standard manner of MCTS search. The policy re(s) is trained with cross entropy loss to fit the softmax across actions over (s, at the root.
5.2 DEEP SEA EXPERIMENTS
The Deep Sea environment structured as grid, where at each time step the agent chooses between two actions, goes right or left and one row down. There is a reward Tgoul 1.0 at the bottom right corner, the agent starts at the top left corner and thus the probability of randomly finding the unique optimal trajectory decays exponentially with the size of the grid. Every transition along the optimal trajectory receives a negative reward that is negligible in comparison to the goal reward, but is otherwise the only reward the agent sees, actively discouraging exploration along the optimal path. The action mappings are randomized such that. the effect of the
action is different in different states, preventing the agent from generalizing across actions. To evaluate FMCTS in the presence of deterministie transitions and stochastic rewards that more generally align with the assumptions in Section we include a custom stochastic-reward variation of Deep Sea where the goal reward Tooo! ~ (L,, 1), and reward Tmislead (o 1) is given at the bottom left corner. The agent must explore both transitions a sufficient number of times to correctly identify the larger mcan reward. Rosults are presented Figure 2
Sceling Dilfeeent Deep Sen Sizes
Stochesti-lloard Deep See 50x50
Sensitivlly Exploration Patemeter
cstiritted AZ, 22.2
E.AZ (MID)
1.0
5.42 (MD)
und 50% avering mgees
10"
EAZ JINDI
A2 USB (AND)
AZ+UBE (MUD)
AZ
ENZ (Courtal
Experted Buniobnn Ketmm
8DON
MT+URE Xownne)
BOOK
201
0.6
0.4
0.2
10
20
30
10000
20000
30000
40000
0.0
20
12a
152
125
107
Deepliee Stme
Enviremment
Figure 2:
Left: Scaling to growing Deep Sea sizes, 5 seeds per point. Only 2 seeds of MBE were able solve size 40, and none size 50 within the training budget, both marked with an X. Middle: Stochastic-reward Deep Sea 50x50, 10 seeds. Right: The effect of the exploration parameter in Deep Sea 30x30, 3 seeds per point. Mean and standard error.
9

---

Published as a conference paper at ICLR 2025
The left subplot shows sample complexity measured as number of interactions until 90% regret is reached against the size of the Deep Sea environment to demonstrate that the scaling is sub-exponential as expected from deep-expooration methods. The middle subplot presents expected return in evaluation episodes in the stochastic-reward variation of Deep Sea. In the right subplot, the sensitivity to the exploration parameter / is studied and the ability of the agent to learn stably from off-policy data. In Appendix [ we include additional results, including visualization of the uncertainty estimated by EMCTS.
To answer the research questions the following agents based in A/MZ are compared: (i) E-A/MZ (purple, dashed for AZ and dotted for MZ), our method. The agents use EMCTS with counts RND to estimate reward and transition uncertainty and UBE to estimate value uncertainty, search with EUCT and act with the action with the most visitations at the root. (ii) Baseline AZ (orange) explores by sampling actions proportionally to visitations at the MCTS root. AZ included for reference, to demonstrate that indeed Deep Sea cannot be solved in reasonable time with random exploration, and is not able to solve any of the environments in the alloted training steps, with the exception of one seed in the smallest environment size, and that only because the initial replay buffer by chance already contained a trajectory that reached the goal. We include the exponentially-scaae performance expected of randon-exploration based methods such as AZ, for reference. (iii) Last, A/MZ+ UBE (red) acts with a similar UCB-explorat ion objective to that of EP BP/UCT, but does not search with the uncertainty (see Appendix D.8. AZ-based agents are given access to the true transition model. The value model is learned, as well as the reward model to investigate the behavior under the most general setting considered in Section 3.3 All A/MZ agents are trained with targets generated by Reanalyze. For reference performance on Deep Sca, we include Bootstrapped DQN (BDQN, Osband et al. 2018). popular model-free, non-search based deep exploration approach that relies an ensemble to drive deep exploration directly. For full implementation details see Appendix D
As expected for deep exploration methods, agents that are informed with respect to epistemic uncertainty (E-A/ML) MZ, A/MZ+UBL and BDQN) demonstrate sample efficiency that scales sub-exponentially with environment size (Figure 2 left). In addition, E-AZ is able to solve Deep Sea in the presence of stochastic rewards (Figure 2 middle). This answers RQ I: EMCTS successfully demonstrates deep exploration in the presence of learned value, reward and transition models as well as both deterministic and stochastic rewards. E-A (Figure 2 left and middle plots, purple) demonstrate significant improvement in sample elliciency over the equivalent agents that do not. use search (red), in deterministic and stochastic reward environments and even with the learned transition model of MZ (dotted line). This answers RQ II: EMCTS demonstrates benefits from search for uncertainty estimation and exploration which is retained in the presence of MZ's lcarned transition dynamics' model. The low regret in evaluation with exponentially increasing values of B (Figure 2 right) demonstrates that the agent can stably learn the optimal policy even in the presence of off-policy exploratory data.
CONCLUSIONS
In this work we present EMCTS, novel, practical and theoretically motivated method to incorporate the epistemic uncertainty from learned models into MCTS, as well as harness the search for deep exploration. AZ paired with EMCTS (E-AZ) achieves significantly higher sample efficiency in the sparse-reward, challenging task of programming in the Assembly language SUBLEQ, compared to baseline AZ. In the popular hard-exploration benchmark Deep Sea, E-A/MZ demonstrate deep exploration by solving variations of the task which cannot. be solved by baseline A/M2 MZ at all in a reasonable amount of samples. EMCTS' scarch demonstrates significantly improved epistemic uncertainty estimation through more sample efficient exploration over an otherwise equivalent method that does not use search. With EMCTS, A/MZ are much better equipped for sparse-reward and hard-exploration environments, which come up in realistic settings such as algorithm design, where AZ has already made significant advances. By making A/MZ uncertainty aware, EMCTS is also promising for settings that require improved reliability in the face of the unknown such as offline RL, and off-policy target generation.
10

---

Published as a conference paper at ICLR 2025
ACKVOWLEDGEMENTS
We would like to thank Marco Loog, Frank van der Meulen, Itamar Sher, Moritz Zanger, Pascal van der Vaart, Joery Vries & Jinke He for many fruitful discussions and helpful com- ments. We acknowledge the use of computational resources of the Delu supercomputer, provided by Delft High Performance Computing Centre (https:// httw//wwwtt/tt tudelft. nl /dhpc) as well as the DAIC cluster. This work partially supported by the EU Horizon 2020 programme under grant number 964505 (Epistemic AI), and partially funded by the Dutch Research Dul-of-Disbributian Distribulion Generulizalion in Deep Reinforcement Council (NWO) project Reliable Oul-of-
Learning with project number OCENW.M M.2. 21.23..
REFERENCES
Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM J. Math. Anal. 43(2):904499) -994944,4,,99 2011. doi: 10.1137 100805441
Ioannis Antonoglou, Julian Schrittwieser, Sherjil Ozair, Thomas K. Hubert, and David Silver. Planning in stochastic environments with a learned model. In The Tenth International Conference on Learning Represenlalions, TCLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, 1CML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. (03-272. PMLR, 2017.
Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, (5):679 (807,966444111 1957.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milng and Qiao Zhang, JAX: composable transformations of Python+ programs, 2018. URL httt:://itte http//gttttuut..//// cow cooon//ooge//axx
Cameron Browne, Edward Jack Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, and Simon Colton. A survey of Monte Carlo tree search methods. IEEE Trans. Comput, Intell. Al Games, 4(1):1 43, 2012. doi: 10.1109/TCIAIGE 201.AAC........11.....
Yuri Burda, Harrison Edwards, Amos J. Storkey, and Oleg Klimov. Exploration by random network distillation. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA,, USA, May 6-9, 2019. OpenReview.net, 2019.
Kamil Ciosek, Quan Vuong, Robert Tyler Loftin, and Katja Hofmann. Better exploration with Optimistic Actor Critic. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Brus Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancowver, BC, Canada, pp. 1785- 1796, 2019.
Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with gumbel. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.nee, 2022.
DeepMind, Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Hennigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent
11

---

Published as a conference paper at ICLR 2025
Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojevic, Wojciech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http:://gitub. wtw.deemm/ddeeeneeeeeeeeeee
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Nomera-Paredes Mohammadamin Barekalain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrillwieser, Grzegorz Swirsazz, David Silver, Demis Hassabis, and Pushmeet Kohli. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-55) 2022. doi: 10.1038 s41586- 022-051722 05172-4.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, TCML, 2018, Stockholmsmüssonn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1582 1591. PMLR, 2018.
Seyed Kamyar Seyed Ghasemipour, Shixiang Shane Gu, and Ofir Nachum. Why pes- simistic? estimating uncertainties for offline RL through ensembles, and why their indepen- dence matters. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint (KK::1812.00900 2018.
Mikael Henaff. Explicit explore-cxploit algorithms in continuous state spaces. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'AlcheBBuc, Emily B. Fox, and Roman Garnett (ods.), Advances in Neural Information Processing Systems 32: Annual Conference on Newral Informalion Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 9372 9382, 2019.
Todd Hester and Peter Stone. Intrinsically motivated model learning for a developing curious agent. In 2012 IEEE International Conference on Development and Learning and Epigenetic Robotics, ICDL-EPIRIE 2012, San Diego, CA, USA, November 7-9, 2012, pp. 1-6. IEEE, 2012. doi: 10.1109 DE//DEEVELLNIII 200.6600002..
Eyke Hüllermmier and Willem Wacgeman. Alcatoric and epistemic uncertainty in machine learning: An introduction to concepts and methods. Machine Learning, 110(3):457 506, 2021.
Ola Hössjer and Arvid Sjölander. Sharp lower and upper bounds for the covariance of bounded random variables. Statistics Probabilily Letters, 182:109323, 2022. ISSN 0167-7152. doi: https://doi.org 10.1006/j.sp..22221099333
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 11:1563-1600, 2010. doi: 10.5555 1756006. 1859990..
David Janz, Jiri Hron, Przemyslaw Mazur, Katja Hofmann, José Miguel Hernández-Lobato and Sebastian Tschiatschek. Successor uncortainties: Exploration and uncortainty in temporal difference learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygekzimer, Florence d' d'Alché-Buu Buch Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4509- 4518, 2019.
Chi Jin, Zeyuan Allen Zhu, Sébastien Bubeck, and Michael I. Jordan. Is Q-learning provably efficient? In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò
12

---

Published as a conference paper at ICLR 2025
Cesa-Biancho and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp.
2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforce- ment learning with linear function approximation. Math. Oper. Res., 48(3):1496 142211199-1 2023. doi: 10.1287 00288/MMOOR.. MM0R.2022.1300
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (cds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Levente Kocsis and Csaba Szepesvári. Bandit based Monte- Carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, Proceedings, volume 4212 of Lecture Notes in Computer Science, pp. 2006. doi: 10. 111000/118771 11877111878422 29.
Springer,
Sotetsu Koyamada, Shinri Okano, Soichiro Nishimori, Yu Murata, Keigo Habara, Haruka Kita, and Shin Ishii Pgx: Haaddware-acceleattee parallel game simulators for reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Sacnko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neural Informalion Processing Systems 2023, NewrIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning, In Hugo Larochelle, Marc'Aurelis Ranzato, Raia Hadsell, Maria-Florins Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 39: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnelt, (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6402 6413, 2017.
Nathan Lambert, Markus Wulfmeier, William Whitney, Arunkumar Byravan, Michael Bloesch, Vibhavari Dasagi, Tim Hertweck, and Martin Riedmiller. The challenges of exploration for offline reinforcement learning. ar preprint arXiv:2201.1186; 2022.
Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2017.
Kimin Loe, Michael Laskin, Aravind Srinivas, and Picter Abbeel. SUNRISE: A simple unified framework for ensemble learning in deep reinforcement learning. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Evenl, volume 139 of Proceedings of Machine Learning Research, pp. 6131 6141. PMLR, 2021.
Owen Lockwood and Mei Si. review of uncertainty for deep reinforcement learning. In Stephen G. Ware and Markus Eger (eds.), Proceedings of the Fighteenth AAAT Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2022, Pomona, CA, USA, October 24-28, 2022, pp. 155-162. AAAI Press, 2022.
Carlos E. Luis, Alessandro G. Bottero, Julia Vinogradska, Felix Berkenkamp, and Jan Peters. Model-based uncertainty in value functions. In Francisco J. R. Ruiz, Jennifer G. Dy, and Jan- Willem van de Meent (eds.), International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valnniia, Spain, volume 206 of Proceedings of Machine Learning Research, pp. 8029 8052. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2025
Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang, Rene Claus, Ching- Chiang, Cheng Chen, Jingning Han, Angie Chen, Daniel J. Mankowitz, Jackson Broshear, Julian Schrittwieser, Thomas Hubert, Oriol Vinyals, and Timothy A. Mann. MuZero with self-competition for rate control in VP9 video compression. arXi preprint or 2xx:2202.06666 2022.
Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Paduraru, Edouard Leurent, Shariq lqbal, Jean- Baptiste Lespiau, Alex Ahern, Thomas Koppe, Kevin Milliknn, Stephen Gaffney, Sophie Elster, Jackson Broshear, Chris Gamble, Kicran Milan, Robert Tung, Minjac Hwang, Taylan Comgil, Mohammadamin Barekatain, Yujia Li, Amol Mandhanc, Thomas Hubert, Julian Schrittwieser, Demis Hassabis, Push- meet Kohli, Martin Riedmiller, Oriol Vinyals, and David Silver. Faster sorting algorithms discovered using deep reinforcement learning. Nature, 618(7964):251 263, 2023. doi: 10.1038/ 018888/4418666 s415564-600 000-860023-000 020-0200--9-99
Oleg Mazonka and Alex Kolodin. A simple multi-processo computer based on subleq. arXiv preprint N0v: 2593, 2011.
John Mern, Anil Yildiz, Zachary Sunberg, Tapan Mukerji, and Mykel J. Kochenderfer. Bayesian optimized Monto- Carlo planning. In Thirty-Fifti AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- Third Conference on Innovative Applications of Artificial Intelligenee, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virlual Event, February 2-9, 2021, pD. 11880 11887. AAAI Press, 2021. doi: 10.1609/ AAALV33518.111
Alberto Maria Metelli, Amarildo Likmeta, and Marcello Restelli. Propagating uncertainty in reinforcement learning via Wasserstein barycenters. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'AchhéBue,, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Conado, pp. 4335 4347, 2019.
Thomas M. Moerland, Joost Brockens, Aske Plaat, and Catholijn M. Jonker. Model-based reinforcement learning: A survey. Found. Trends Mach. Learn., 16(1):1-118, 2023. doi:
Gergely Neu and Ciara Pike-Burke. A unifying view of optimism in episodic reinforcement learning. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiees Lin ), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Brendan O'Donoghue, Ian Osband, Rémi Munos, and Volodymyr Mnih. The uncertainty Bell- man equation and exploration. In Jennifer G. Dy and Andreas Krause (ods.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmäs- san, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3836 3845. PMLR, 2018.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annuul Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 1003-3011, 2013.
lan Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8626 8638, 2018.
14

---

Published as a conference paper at ICLR 2025
lan Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvári, Satinder Singh, Benjamin Van Roy, Richard S. Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. In 8th International Conference on Learning Representations, TCLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nen 2020.
Tiberiu Popoviciu. Sur les équations algébriques ayant loutes leurs racines réelles. Mulhe- malica, 9(129-145):20, 1935.
Aditya A. Ramesh, Louis Kirsch, Sjoerd van Steenkiste, and Jürgen Schmidhuber. Exploring through random curiosity with general value functions. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrIPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3):203 200-2300-, 2011.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, Chess and Shogi by planning with a learned model. Nature, (607789))604460000 2020.
Julian Schrittwieser, Thomas Hubert, Amol Mandhane, Mohammadanin Barekatain, Ioannis Autonoglou, and David Silver. Online and offline reinforcement learning by planning with learned model. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 27580-27887 27591, 2021.
Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In Proceedings of the 37th International Conference Machine Learning, 1CML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 8583 8592. PMLR, 2020.
Pranav Shyam, Wojeiech Jaskowski, and Faustino Gomez. Model-based active exploration. In Kamalika Chaudhuri and Ruslan Salakhut (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5789- PMLR, 2019.
David Silver and Joel Veness. Monte-Carlo planning in large POMDPs. In John D. Lafferty, Christopher K. I. Williams, John Shawo-Taylor, Richard S. Zemel, and Aron Culotta. (cds.), Advances in Neural Information Processing Systems 23: 24th Annual Conference on Newral Information Processing Systems 2010. Proceedings of meeling held 6-9 December 2010, Vancowver, Brilish Columbia, Canada, pp. 2164 2172. Curran Associates, Inc., 2010.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement. learning a algorithu that masters Chess, Shogi, and Go through self-play. Science, (62(6)61))
2018
Malcolm J. A. Strens. A Bayesian framework for reinforcement learning. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 July 2, 2000, pp. 943-950 Morgan Kaufmann, 2000.
Yi Sun, Faustino J. Gomez, and Jürgen Schmidhuber. Planning to be surprised: Optimal Bayesian exploration in dynamic environments. In Jürgen Schmidhuber, Kristinn R. Thórisson, and Moshe Looks (eds.), Artificial General Intelligence - 4th International Conference, AGT 2011, Mountain View, CA, USA, August 3-6, 2011. Proceedings, volume
15

---

Published as a conference paper at ICLR 2025
6830 of Lecture Notes in Computer Science, pp. 41-51. Springer, 2011. doi: 10.1007/ 978-3-642-22 242-2288-222-
Zachary N. Sunberg and Mykel J. Kochenderfer. Online algorithms for POMDPs with continuous state, action, and observation spaces. In Mathijs de Weerdt, Sven Koenig, Gabriele Röger, and Matthijs T. J. Spaan (eds.), Proceedings of the Twenty- ThoettyEightt International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft, The Netherlands, June 24-29, 2018, pp. 259-202900 263. AAAI Press, 2018.
Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mandziuk. Monte Carlo Tree Search: a review of recent modifications and applications. Artif. Intell. Rev. 56(3): 2497-2562, 2023.
doi: 10.1007 /S10/42---0222 022 10228-Y.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. #exploration: A study of count-based exploration for deep reinforcement learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advonces Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 7753-2762 2017.
Gerald Tesauro, V. T. Rajan, and Richard B. Segal. Bayesian inference in Monte- Monte-Carlo Tree Search. In Peter Grünwald and Peter Spirtes (eds.), UAI 2010, Proceedings of the "wendy-Sixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, July 8-11, 2010, pp. 580-588. AUAI Press, 2010.
Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 6306 6316,,31,--0 2017.
Yue Wu, Shuangfei Zhai, Nitish Srivastava, Joshua M. Susskind, Jian Zhang, Ruslan Salakhutdinov, and Hanlin Goh. Uncertainty weighted actor-critic for offline reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 11319 11328. PMLR, 2021.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering Atari games with limited data. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Newral Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrIPS 2021, December 6-14, 2021, virtual, pp. 25476 25488, 2021.
Qi Zhou, Houqiang Li, and Jie Wang. Deep model-based reinforcement learning via estimated uncertainty and conservative policy optimization. In The Fourth AAAI Conference Artificial Intelligence, AAAI 2020, The Therty-Sccond Innovotive Applications of Artificial Intelligence Conference, IA 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. AAAI Press, 2020. doi: 10.1609 10.1609/AAAI, 134144441446677
16

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RESULTS
A.1 PROOF THEOREM 1
For clarity, let us again define xt as the policy that is optimal in the true environment n² arg max, Q and Th the policy that is optimal in specific model M, that is "h arg max, 2x By the definition of the model, we have [[M] m, where m is the true model the environment. Therefore Q =: Q = PiiM = E Bx 197) by linearity of the value in the reward function. By Chebyshev's incquality:
1 S Oi + V V VI 21-8
(14)
The right-hand side term 2h + VBV
Mr is hard to estimate among other reasons because the optimal policy is not known. But it can be upper bounded as follows:
1 V
V
0 V8 [
I max 2h + V8 VOO)
"
which holds because the right- hand side is the maximum possible policy in set that contains
n..
Putting the entire set of inequalities logether, we arrive at:
p(Qr= 1 1 S 2h + to MQ s max 2 + 1
V8 V V(2
2 21-6.
(15)
and thus: p(Q' S max 2 + v8 1(0%) 1)
2 1 5, (16)
QED Theorem 1
A.2 DERIVATION OF THE UPPER BOUND ON (IE
By definition,
Via a)] = V = Σ Cov(l' (sk, a), (st,
(17)
In A A/MZ it is standard to learn set of deterministic models V, R and use them throughout planning, and therefore v², شd cannot be assumed to be independent Vi + j. Had they been independent, one would compute the variance of the sum directly with the sum of the variances. Instead, we use the inequality for covariances with known variances (Hössjer & Sjölander b022): Cov[X,Y] < VV[X]V[Y] to upper bound the variance Vly (sk;a)]:
Viaxz a)] = "VEVve
= = Σ Cov Cov(v a), o (s),
(18)
1 Σ V/u a)) (sk, = VVVVVi a)l $ n2 k--1
(19)
In other words, the standard deviation of the averaged backup v Viq (sk, a)] upper bounded with the averaged standard deviation across backups + VV a)]. The first
incquality due to the incquality for covariances with known variances, and the following equality is sum of squares.
A.3 EMCTS WITH LEARNED TRANSITION DYNAMICS
When the transition function j is learned, we must formulate it as a random variable f as well. We note that in this case
F(S,a) is a random variable that depends on the distribution of the previous state S propagated through the uncortain transition function F, and similarly the distribution of S' will propagate through the reward and value and future transition predictions R(S",,) a), V (S'), F(S", a). Tn other words, in order to estimate V(Q",) M
17

---

Published as a conference paper at ICLR 2025
we need to account for propagation of the variance through the Markov chain, which is an expensive and non-trivial process. In addition, as the value is non-linear in the transition dynamics f, Theorem II does not apply and Equation is is not upper bound with specific probability. Finally, to extend EMCTS to MZ. fully, we must account for the fact that the dynamics model learned by MZ is not operating in the true state space of the environment, but in a Salue-equivalent abstraction. To extend EMCTS to the learned dynamics case, we will assume that is possible estimate epistemic uncertainty in the abstracted state space S in a meaningful way. This problem can be circumvented by driving additional losses through the learned model that incentivize distinguishing between unique states in latent space (Henafi 2019), or by learning an auxiliary dynamics model distinguish between sitiing-statt---d-attio------ess
which has been used successfully by Sokar et al. (020). We will therefore use the notation of states or S in the tree, whether they are in the true state space of the enviromment S or the abstracted space of MZ S. In addition, since standard MZ. plans with deterministic transition model, we extend EMCTS to the setting where either the underlying transition dynamics / are deterministic, or the abstracted deterministic transition function is sufficiently meaningful. For simplicity, let us further assume that the state space S is continuous, and the starting state distribution is over a finite domain.
novel and observed
To circumvent the problem of the propagation of state uncertainty through the Markov chain, we propose cheap and simple maximmally-optimisti alternative upper-bound approximation for V[Q We note that: (i) F, R are trained on the same data and thus when the epistemic variance over one of the two is maximal the other can be expected to be maximal as well. (ii) We have assumed a deterministic true transition function f and thus the variance in F can be modelled as maximal on the unknown and zero on the known. (iii) If the uncertainty in the prediction of any state (SF( a)] 2 O, we expect the uncertainty in all future predictions Sj along this trajectory j > l to be associated with maximal uncertainty. We use these observations to formulate the following simple approximation:
V[R(Sk; a)) R V(N(SH,,)) VSV)( R VsE)() V(s,a) ED
(20)
()) mann (S)) ~ (1), where j 2 k and V(s,a) &D (21)
That is, we propose to ignore any uncertainty in transition along zero-uncertainty trajectories, and with the first uncertain transition, to assume all uncertainties are maximal for all predictions in the rest of the trajectory. To identify whether (s.a) & DD we can directly use V[R(s, a)], where V[R(s, a)] ~ 2an indicates (s, a) & D. This will guarantee that (given that the mechanism to identify unobserved transitions is sufficiently reliable) the agent remains sufficiently optimistic and the planning objective of EP EP/UCT remains an upper bound on Q' We note that in practice, while this approach is theoretically sound, the results of the experiments in Section 5.2] in the presence of reliable transition-umeeraannn not necessary and the regular setup of EMCTS is sufficient for deep exploration even in wwwpuuaallnt-asstaraeeee
motivate that it
the presence of a learned, i(s,a) a) is a sufficiently reliable estimator of novelty in the environment.
transition model, given that
B ADDITIONAL EXPERIMENTS
We include an example comparison of the uncertainty estimated by EMCTS to that of the uncertainly estimator used by EMCTS, the UBE network head, in Figure 3 The E-AZ agent used in this experiment uses the true transition model but a learned reward as well as value functions, matching the setup of Section 3.1 The Deep Sea environment is presented as a grid, where states are the cells including and below the diagonal. Bold blue in the grids in the bottom row (inverse counts) indicates unvisited states. By averaging across multiple predictions in search, the uncertainty estimated by EMCTS (top row) is much more varied, more accurately associating less more uncertainty with states that lead into observed unobserved trajectorics respectively, compared to the UBE predictions (middle row). Most importantly from the perspective of exploration, EMCTS associates larger uncertainty with states that lead into unobserved directions much more consistently than the single predictions of UBE for each state (for an easily visible example, t= 2000, top of the diagonal).
18

---

Published as a conference paper at ICLR 2025
EMCTS Surevilue Unoetairyy Pradiction
5-3
1- 1043
1-:000
1- 5800
50
20
0.0
USE Stete-UNiue Uncerblitt Fredectis
60
40
30
10
0.0
2.0
1.5
1.0
0.5
Figure 3: Heal maps over states in DeepSea 40 by 40 al different times (columns) during an example training run of EMCTS with an AZ transition model. Upper row: value uncertainty at the EMCTS root node. Middle row: single prediction of UBE at each state. Lower row: inverse visitation counts as reliable local uncertainty, where score of 2.0 represents unvisited.
We include addition detailed evaluation curves for E-A/MZ, A/MZ and A/MZ+ UBB in Figure 4 as well as rate-of-exploration (number of unique states encountered per interaction with the environment). An additional variation of MZ is included in this Figure, where instead of value-equivalent abstraction the model is trained with a reconstruction loss to match the true transition function and observation space of the environment, such that f(s, a) = 8' zs s'. By training the RND estimator only on true transitions (s,a) a) and evaluating it online on iransitions predicted by the learned transition model (8', a'), 8' f(6, a), this agent. incentivized to estimate the uncertainty over every uncertain transition (s, & D as maximal, implicitly implementing the approach described in Appendix [A.3] For implementation details Appendix D.3 In all figures, E-A /MZ outperforms the other agents both in rate of exploration as well as in their ability to learn to reach the goal. The most interesting bchavior is perhaps that of the reconstruction based model, that does not search the environment siguificantly faster than the other baselines, and yet learns to reach the goal much earlier (bottom row in Figure 4). We hypothesize that due to the search, the uncertainty estimated by the agent is more reliable, resulting in identifying the correct action that leads into novel states, more times purple curve remains the highest for quite a while, before all others curves match it, despite all curves being very close throughout most of the training.
row. Just visible on the right-hand plot, one can see that indeed the
We include a table evaluating interactions-to-gon results demonstrate that even when the learned dynamiis model not designed for planning (anchored model, third block, Table [], EMCTS is able to find the goal much faster.
on Deep Sea 40x40 for all agents. The
Finally, we include a comparison between F-AZ and AZ on MinAtar Figure The uncertainty estimator is the full-Hash used for SUBLFQ, which uses hash based counting to distinguish between any two unique states. This demonstrates that even when the uncertainty estimator is unsuited, and even without tuning the exploration paraneter 3 = 0 (in Figure B = 1.0 as in the SUBLEQ experiments), EMCTS can compare well to the bascline.
19

---

Published as a conference paper at ICLR 2025
AZ Transition on Model
800
states
600
0.50
AZ+UBE (RND)
AZ
0.25
sizo
maximum
30000
30000
Environment steps
Environment steps
Model
Discovered
660
E-MZ (counts)
Eplandi
0.50
HZ UUB (counts)
400
BDQN end ensemm size 10
10000
20000
30000
40000
10000
20000 Environment
30000
40000
Environment
Reconstruction Loss Transition Model
800
0.75
600
E-MZ (AND)
Epicodic
0.50
MZ+UUB (RND)
400
HZ
BDON ens enm..m... size 10
200
0.00
0
10000
20000
30000
40000
0
10000
20000
30000
40000
Environment
Environment
Figure Deep Sea 40x40, mean and standard error for 20 seeds. Rows: Different transition models. Left: episodic return in evaluation vs. environment steps. Right: exploration rate (number of discovered states vs. environment steps).
Table 1: Number of environment steps until the first visitation to the goal transition.
Average steps to goal transition for seeds that discovered goal + STD
% seeds that discovered goal
Novelty Estimator
Exploration
E-AZ
10539 9006
94% 35 seeds
RND
AZ+UBE
22801 = 7514
91% of 35 seeds
AZ
0% of 20 seeds
E-MZ
14339 + 6845
100% of 23 seeds
Counts
MZ+UBB
29945 = 8113
57% of 21 seeds
MZ
0% of 20 seeds
E-MZ
15241 3236
95% 20 seeds
Reconstruction Model (RND)
MZ+UBB UBE
22497 = 6645
85% of 20 seeds
MZ
0% of 20 seeds
C SUBLEQ
What follows is a formal charactcrization of SUBLEQ as used in our experiments, and example programs for the two tasks we presented.
For SUBLEQ-N, have memory made up of N words (Wo, W1, w where each word w; is an integer from O to N inclusive (we write w; E [0, N - 1J). We also have an input sequence (No, 01, ...,, ii E [0, N - 1), of variable finite length depending on the particular task to be solved. Tasks correspond to different algorithms
want the agent to implement. Lastly, there is an output buffer (uo, uI,...,, u, E N - which begins empty, but can be extended with output values during exccution of SUBLEQ program.
We refer to w; as the word at address i. Additionally, we give names to some specific addresses: CIN N - 3, @DUT N - 2, @HALT = N - 1. The program is stored contiguously in memory starting at address instruction to execute is (wo, W1, w2).
Execution begins from address as well, meaning the first
20

---

Published as a conference paper at ICLR 2025
minataraslenic
minalat-freaer
minal wakoud
1.-
27.5
35
Ao.ayaeab Braaudnn Retum
1.6-
40-
25.0
22.5
Eusustionn
25-
20-
12
20.0
20-
2.-
20-
17.5
10
E-AZ AZ, sescan10
EAAZ
6-12
6-12
12.5
Endmnomen steps
steps
Figure 5: Mean and two standard errors for 10 seeds.
When executing some instruction at address i, we look at the three words (wi, Wi+ W;42), and modify the memory by subtracting the value at address w from the word at address wt i.. Ww, f Ww, Wwaer We say that this instruction reads from w; and Wi+1: and writes to Wyy We also say that reading from returns Was. All operations are done modulo N so that the words remain in the range [0. N 11. If the result before modulo was less or equal to zero, execution continues from address Wx+2 (we say we jump to wc+2), meaning the next instruction would be (Weses) Ww,42+1, 2w,) the result before modulo was strictly positive, then the next instruction is the next three words, i.e. (w143, W444, W:+5).
Interacting with the addresses @IN, @OUT, and @HALT has different behaviour than normal execution. Reading from the address @IN will instead read the next number from the input sequence. The first read from eIN will return vo: the next read returns 11, etc. Reading from the input sequence when there is no next value will return 0 instead. Writing to @IN is ignored.
Reading from @OUT always returns a O, but writing to @OUT will write to the output buffer. We say that we output the value. Each value that we output is added to the output buffer, so after the first output un, the buffer looks like (uo), after the second output u1, it is (uo, u1), etc.
The output buffer is compared against the desired output for the task to determine whether the task was solved correctly. The first incorrect output terminates the program and results in a failure of the task. If the output buffer ever equals the desired task output, the program terminates and the task is solved successfully. Finally, if the program tries jumping to an address where the instruction would overlap @HALT, such as (WaIx, WaDUT, Weuur), the program terminates.
When using SUBLEQ-N as a reinforcement learning environment, the agent writes a program one word at time. It. gets to observe the current state of the memory before execution (it is just the program it has written up to that point followed by zeroes), an example input and desired output pair for the given task, and the resulting state of the input sequence and the output buffer after executing the currently written program.
At each state, the agent has N actions {0, N 1}, each corresponding to writing that number into the next location in memory. The memory is initially filled with zeroes. After an action is chosen, the number is added to memory, and the currently written program is executed to determine the states of the input and output on the example test as well as other (hidden) test cases. If all test. cases succeed, the episode terminates after one more (irrelevant) action. On the other hand, if the agent reaches the end of writable memory (N 3 actions), the episode terminates unsuccessfully.
The Negate Positives task expects a program which receives positive integers and outputs that input, expect negated. This task are very simple, since it can be done with a single instruction: Reading from @IN will subtract the next input from whichever address to which we write. If we write to @OUT, which reads as O, we are effectively writing 0- 22 = -. For Negate Positives, this is exactly what is required, so the only remaining challenge is how to loop back the start. Luckily, since we know the input is always positive, the output will be negative (or zero), so always jump. Thus, if we choose the jump address to be 0, we can also loop to the start in the same instruction.
21

---

Published as a conference paper at ICLR 2025
(@OUT, OIN, O,...) in memory forms solution the task, and since the memory is initialized with zeroes, it only requires the agent to write 2 words, meaning only actions.
In code, solution to Negate Positives looks like this:
@start:
subleq @OUT @IN @start
Which the agent would write as: (N-2, N-3,
In the Identity lask, we require a program which outputs the input unchanged. This is slightly more difficult that Negate Positives, because an instruction in SUBLEQ always subtracts, so we need at least two instruction to undo the negation. This can be done by storing the return of @IN some auxiliary word, and then writing that value to output. Let us denote the address at which we store the value temporarily could begin (@x, @IN, 3, GOUT, ax... Note the 3 at address second instruction regardless of whether the input is positive needed to progress to the negative. This program would work for the first imput, but we must produce a program which loops. Thus, we still need to erase the value stored address @x (to prepare it for the next write), and must loop to the start. These two things can be done in the same instruction. We arrive at a program like (@x, @IN, @OUT, @x, 6, @x, @x, 0,--). The last instruction (@x, @x, 0) clears @x and jumps to address zero (since wax < wax wax O which & 0). Again, we required the constant at address to unconditionally continue to the next address. In general, an agent would need 8 actions to solve Identity, where it needs to pick @IN, GOUT, 3, and specifically, and ncods make sure that all of @x are the same. We say in general, because there is actually a clever solution when we choose @z = O. In that case, the program becomes (0, @IN, 3, COUT, 0, 6, 0, 0, 0.... which only requires the agent write 6 words, since the memory is initially filled with zeroes.
@x. The program that solves Identity
In code, a general solution Identity looks like this (left in human syntax, right as the agent writes, the 9s can be any constant 2 9, < N):
@start:
subleq @x CIN subleq @OUT @x subleq @x @x @start
(9, N-3, 3)
(N-2, 9, 6) ; (9, 9,
@x: .data 0
( ...)
While the shorlest (known) solution (in terms of non-zero bytes writlen) looks like this:
@start:
subleq 0x:0x @IN subleq 2OUT @x subleq @x @x @start
(0, N-3, 3)
; (N-2, 0, 6) (
D IMPLEMENTATION DETAILS FOR DEEP SEA
Our implementation for the Deep Sea agents is based in the framework of Ye et al. (021 Below, we detail the implementation details unique to E-A/M MZ and A A/MZ+UBE in Deep Sea.
D.1 TARGETS
Value, policy and reward targets were all computed as in MZ Schrittwieser et al. (2020).
UBE targets were compuled in an n-step manner:
Utarget (st)
Σ 22 m( ac+i)
2 (st+n)
2n
(22)
1=0
22

---

Published as a conference paper at ICLR 2025
Where 7 is the RND / exact hash count-based novelty estimators. To guarantee that the UBE estimates remains sufficiently optimistic, the value-uncertainty bootstrap V(V M (8t4n) was computed in of two ways:
1. Rool largels: The uncertainty at the rool of the EMCTS tree at stale 814n-
2. Non-rool turgels:
VIV (st+n) = max (y ac+n) + 7
(23)
Where
u($e+n+1) max (ū($)+at1), 1
-- (1(((1+n:00tt))
(24)
D.2 LOSSES
The original MZ algorithm three loss functions Ly, Lv, Lo for the reward, value and policy, respectively. The gradients from the losses Lr, Lu, La propagate through the learned transition model f and are the only learning signal that used train the model.
For the anchored model (see Section
we use an additional reconstruction loss:
Lre ΣΣ 1EBN
1 St+e|1
where B = {st, Gg. Tt, S1+1, att1...... Sit is training batch containing b trajectories of length sampled from different episodes, and st the state predicted by the learned model. To simplify model learning with the anchored model, the representation function that was used for the anchored model transforms the observations from 2 dimensional (N, N) one-hot representations to dimensional (2.N) representations where the first N entries are 1-hot vector representing the row and following N entries are a 1-hot vector representing the column. From this perspective, model as a consistency loss between the representation and the state prediction rather than reconstruction loss.
view the Lre loss that used to train the anchored
To estimate value-uncertainty at the leaves, we train a UBE function a with a UBE loss La:
Cu = 18 ΣΣ butth
target ydt log aj
168K=0
The final loss is computed as:
L: X,G, Xyb Axh Xuf.
Where the coefficients X, Au, An Au used to weigh the relative effects the individual components of the loss have on the learned transition model f. When L. was used (the anchored model in Section 5), the model parameters of were affected only by Tree through a second backwards pass.
D.3 DIFFERENT DYNAMICS MODELS
We describe the three Iransition models used in 5 in more detail. The AlphaZero dynamics model is true model of the dynamics of the environment, in the true state space of the environment. When planning with this model local uncertainty is estimated with RND and value-uncertainty
estimated with UBE. The MuZero model is value-oquivalent model in latent space. f are learned by the agent during training from the value, policy, reward and UBE losses. When planning with this model local uncertainty is estimated with state-visitation-coume Amchored-MuZZen transition model trained only to predict the true transition dynamics of the environment through reconstruction loss L (see Appendix D.2 When planning with this model local uncertainty estimated with RND and value- uncertainty estimated with UBE.
(see D.5 and value-uncertainty is estimated with UBE. The
23

---

Published as a conference paper at ICLR 2025
D.4 PLANNING WITH RANDOM NETWORK DISTILLATION BASED EPISTEMIC UNCERTAINTY
In order to estimate the epistemic uncertainty a transition 77s, RND Burda et al. 2019 take as imput state and action and computes (2(Ø(s, o' (s, a)) between two neural networks Φ, d'. o' is kept stationary, while & is trained with the same loss that evaluates the uncertainty. When the planning is done with true model, the agent has access to the true states 8++k- When the planning is done with the anchored model, the latent states outputted by the transition model & approximate the true states 9144 which allows over (8f, 0x+2). In both cases, RND is trained only over the observed transitions (Se+Rs ar4sk); not latent state representations (5) ac+k), to achieve the objective of yiclding large RND prediction errors the further the latent state prediction 8 is from observed state S1+kk
use RND
D.5 PLANNING WITH VISIIATION-COUNT BASED EPISTEMIC UNCERTAINTY
When planning with the abstracted model, we provide the agent with access to two additional mechanisms that used only for local uncertainty estimation: the true model of the environment and a state-action visitation counter C(st,aa), During planning, the true transition model follows the planning decisions agt+k and keeps track of the true state st4k- When the agent evaluates the local uncertainty with transition ($) a(+k) the true model provides the matching true state 8t+k to the visitation counter, which produces the local uncertainty based on the following formula:
n[S44k: 0c+k) C(s a(+k) +e
Where > a constant and C(o++k ac+&) counts the number of times the state action pair (St+R, az++&) has been observed in the environment. This allows to evaluate the abstracted-man modell agent the presence of reliable source local uncertainty. The leaf- value uncertainty u($f) (which is the dominating factor in visited areas of the state space, as (55444 d++x) + 0 quickly in observed transitions) relies entirely on the learned UBE function which operates directly latent states s4.
D.6 USING UBE TO ESTIMATE VALUE- UNCERTAINTY AT THE LEAVES
It is essential for exploration that the epistemic uncertainty prediction is reliably high in unobserved areas of the state action space. For this reason, a learned function may not be sufficient to detect that state 8, has not been previously observed. Instead, we use the following:
max (ū(s:), 1 1- 7 x (si))
(25)
If the uncertainty 118,, π (s:)) for the transition (se, (st)) is high, the uncertainty will be estimated as high regardless of the UBE prediction u(s)), and otherwise, either u(st) is high or both are negligible.
D.7 SEPARATING EXPLORATION FROM EXPLOITATION
Acting in the environment with dedicated exploration policy can be expected to result in samples that are very offeexploitation-pllicy Learning from very off-policy data is known to cause instability in training even in off-policy agents. To mitigate that, the EMCTS and UBE agents (see section 5 alternate between two types of training episodes: exploratory episodes that follow an exploration policy throughout the episode (such as policy generated by EMCTS with an exploratory planning objective), and exploitatory episodes that follow the standard Mužero exploitation policy throughout the episode. This enables us to provide the agent with quality exploitation targets to evaluate and train the value and policy functions reliably, while also providing large amount of exploratory samples that explore the environment much more effectively and are more likely to efficiently search for high-reward interactions.
In practice, rather than alternate between exploration and exploitation episodes we run a certain number of episodes in parallel, certain portion of which are exploitatory and the
24

---

Published as a conference paper at ICLR 2025
rest are exploratory. In our experiments the ratio was 50/50. To avoid learning separate prior-policy that may not be necessary in environments with small actions space, we set the policy prediction T($;) (see Equation 3 to uniform over all actions, for all 8 during exploration episodes. Dirichlet noise was not used to drive exploration in MCTS with the UBE and EMCTS agents, as any little amount of stochasticity in the policy can prevent the agent from reliably completing the one optimal trajectory.
D.8 THE A/MZ+UURE AGENT
The A/ A/MZ+UBLL ablation agent uses MCTS to evaluate the value of actions in the same manner as A, A/M and explores by taking the action a, that maximizes the combination of the Q-values approximated by MCTS, local uncertainty V[R] and UBE head u:
(26) 9xr (50, az) are the values at the root of the regular MCTS tree after search. The main difference between A and E-A/MZ is that in E-A/MZ the uncertainty VV a+) + (f(( at)) estimated takes into account estimates from multiple differ- ent future trajectories, in the manner MCTS estimates the values 43
a = arg max 9nz (so, ar) + BV V[A( an) + (
E NETWORK ARCHITECTURE & HYPERPARAMETERS
E.1 HYPERPARAMETER SEARCH
Due to the large number of hyperparameters in the MuZero framework, our optimization process consisted of manual modifications to the hyperparameters used by Ye el. al. (2021) for Deep Sea. and Koyamada. al. (2023) for SUBLEQ with the objective of achieving learning stability on the target environment with the simplest network architectures possible. Two exceptions to this statement are the RND network architecture and scale, and the exploration parameter $.
The RND architecture was designed with the objective of reliably achieving small RND predictions over observed state-action pairs and large predictions over unobserved state-action pairs. The RND scale was tuned with the objective of achieving local uncertainty measures for unobserved state-action pairs that are significantly larger than the minimum reward of Deep Sea.
The 3 parameter in Deep Sea was tuned with the objective that the EMCTS and only- UBE agents will prioritize exploration of the enviromment over exploitation until the entire enviromment has been searched, and was tuned separately for every model.
For SUBLEQ we chose 1. We did not experiment with additional values of B. However, first, the values, UBE prediction, and state- novelyy predictions are all bounded < 1, such that need not account in this case to the possibly arbitrary scales UBE / the novelty estimator. Second, to make the most out of Jax's naturally parallelized setup, each parallel episode explores with a different 3; I B, evenly spacod from 0 to B.
15. NETWORK ARCHITECTURE
The functions f.g, u, n, th, s used fully connected DNNs of varying sizes. The sizes of the hidden layers and output layers are specified in Table 2 for Deep Sea. For SUBLEQ the FC network architecture constituted value, UBE, exploration policy ne and exploitation policy и networks. All networks used two hidden layers of size 256 with ReLu activations between hidden layers. The value head used tanh activation on the last layer, the UBE head used a (.5(tanh(zz) + 1) activation to bound the ube prediction between 0 and 1. The policy heads did not use any activation layers.
25

---

Published as a conference paper at ICLR 2025
Table Network architecture hyperparameters, Deep Sea
True Model
Function
Hidden Layers Sizes
Output Layer Size
g
2256, 256
21
256, 256
21
u
[256, 256
21
[256, 256]
2
Anchored Model
Function
Hidden Layers Sizes
Output Layer Size
1024, 1024, 1024
80
g
r
256,, 256
21
V
[256, 256
21
256, 256
21
2556, 256
2
Abstracted Model
Function
Hidden Layers Sizes
Output Layer Size
1024, 1024, 1024
100
g
512, 512
100
128, 128
21
V
[28, 128
21
128, 128, 128]
21
[128, 128]
2
RND nelwork archilect ure
Function
Hidden Layers Sizes
Output Layer Size
1024, 1024
512
512
512
E.3 DEEP SEA HYPERPARAMETER CONFIGURATION
We detail the full set of hyperparameters in Tables and for Deep Sea. For the BDQN baseline, used the default implementation in https://githu: with ensemble size of 10 and matching batch size to EMCTS: number of unroll steps times batch size 5 256 1230. Otherwise, the default hyper parameters were used.
comm/deepmin//buitta.
E.4 SUBLEQ HYPERPARAMETER CONFIGURATION
The SUBLEQ E- B-/AZ agents are implemented in Jax, based in the implementation of Koyamadal et al. 2023). MCTS parameters used the defaults provided by DeepMind al. (2020).
Detailed lyperparameeer configuration below:
hash: XXHash, 32bit
number of parallel episodes -128
number of E/NCTS simulations 32
batch size 4096
number of times each frame appears in training in expectation = 4
discount 0.97
replay buffer size 200,000
priority exponent of prioritized replay buffer 0.6
learning rate = 0.001
populate replay buffer for N frames before starting training, N 5000
run evaluation episode every N frames, N 20480
number of parallel evaluation episodes = 32
26

---

Published as a conference paper at ICLR 2025
Table Hyperparameters used in the Deep Sea experiments Setting
Parameter
Comment
Stacked Observations
0.995
Number of simulations in MCTS
50
Dirichlet noise ratio (E)
0.3
Root exploration fraction
Batch size
256
Learning rate
0.0005
Optimizer
Adam (Kiggma & Ba 2015
Unroll steps I
5
Value target TD steps (n.)
UBE target TD steps (nw)
value support size
21
UBE support size
Reward support size
21
Reanalyzed policy ratio
0.99
See (Ye et al. 2021
See
Schrittwieser et
2020
Prioritized sampling from the replay
True
Appendix G
See
Schrittwieser et al.
2020
Priority exponent (a)
0.6
Appendix G
See
Schrittwieser et al.
2020
Priority correction (8p)
0.4
Appendix G
Evaluation episodes
8
Min replay size sampling
300
Self-play network updating inerval
5
Target network updating interval
10
Table 4: Specific for models and agents
Setting
Parameter
True Model
Abstracted Model
Anchored Model
EMCTS
UBE
Uninf.
FMCTS OBE Uninf. FMOTS
UBE
Uninf.
Training steps
environment
45K
45K
45K
35K
35K
35K
45K
45K
45K
interactions
Reward loss
1
1
1
1
weight X
Value-loss
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
weight A
Policy-loss
0.5
0.5
0.5
0.5
0.5
weight A
UBE-llss
0.125
0.125
0.25
0.25
0.125
0.125
weight Au
RND scale
1.0
1.0
0.001
0.001
Root based
False
False
False
True
True
True
False
False
False
largets
Disabled
policy
True
True
False
True
True
False
True
True
False
in exploration
Number
parallel
2
2
2
2
2
2
2
2
episodes
Out are exploration
1
1
1
episodes
Exploration
10
10
1
1
10
10
coefficient
Dirichlet noise
0.25
0
0.25
0
magnitude p
27


Reviews:
[{"review_id": "wKyn0CfPiq", "reviewer": "Reviewer_Uotu", "summary": "This work studies epistemic MCTS, which is to characterize the propagation of model uncertainty in tree search. This is motivated by tasks where the model dynamics are not known in advanced, but need to be learned instead. It could be also useful to host exploration methods.\n\nThe algorithm is inspired by theoretical view of linear Q, where the true optimal Q is bounded with high probability by the Q estimate plus the variance term $O\\sqrt{V}$. Though the bound doesn't apply to learned dynamics, it works in the similar way as UCB, where the \"inequality\" provides intuition of the algorithm design. In the search step, the epistemic UCT then uses a similar bonus term in $O\\sqrt{V}$ that is applied to the Q estimate.\n\nThis variance term is also propagated through the backup operator, as the authors intended to in their motivation of this work. Through an independency assumption, the variance could be backed up by variance terms of the nodes on the trajectory. With this backup, epistemic UCT could be applied to obtain epistemic MCTS.\n\nThe algorithm is tested on Subleq, which is a programming task, and Deep sea, which is a gridworld task. Combining with AlphaZero/MuZero, the algorithm performs quite well on the baseline tasks.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The new algorithm solves MCTS with a learned model, with deep exploration and variance propagation.\n2. The model is supported by theoretical insights.\n3. The model performs quite well on the baseline tasks.", "weaknesses": "1. The practical value of epistemic MCTS remains questionable. In what real-world tasks do we need to run search without knowing the world model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GYusbopzFQ", "reviewer": "Reviewer_acfQ", "summary": "This paper proposes Epistemic Monte-Carlo Tree Search (EMTCS) by introducing a method incorporating epistemic uncertainty in traditional MCTS, due to the limited coverage of the data. This paper upper bounds the uncertainty in the MCTS process and designs a novel planning scheme with this estimated uncertainty upper bound. This method makes the agent to explore the environments with sparse reward signals more efficiently. They did experiments on code generation task like SUBLEQ, which involves deep exploration. They also conducted experiments on the Deep Sea Benchmark. Extensive experiments show that EMCTS achieve better sample efficiency and deep exploration compared to baseline methods, particularly in tasks with sparse rewards.", "questions": "/", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides a relatively rigorous theoretical foundation for EMCTS. The authors derive an upper confidence bound for the epistemic uncertain within the learned MCTS model, which theoretically justify the exploration strategy of EMCTS.\n\n2. The experiments demonstrate the effectiveness of EMCTS algorithm in SUBLEQ and Deep Sea task. EMCTS show a better sample efficiency than other baseline methods. Notably, EMCTS demonstrate deep exploration in the presence of the learned value, reward, and transition models as well as both deterministic an stochastic rewards.\n\n3. The motivation of EMCTS is good: to address the epistemic uncertainty in deep exploration tasks and incorporate the uncertainty not just in reward but also in transition dynamics.", "weaknesses": "1. The authors assume consistency across the reward and value. This assumption might not hold in dynamic environments or with certain deep neural network structures in practice. To what degree do those assumptions hold in practice? Are there any experiments results showing that those assumptions hold (or nearly hold) in practice? How does EMCTS handle potential inconsistencies in epistemic uncertainty when the learned models (reward, value, transition) are not fully aligned?\n\n2. The upper bound of the epistemic uncertainty only applies to the discrete state-action space and can introduce considerable computational costs if we are in a high dimensional space. Moreover, how does EMTCS handle larger state-action spaces or continuous state-action spaces? Experiments in the paper only show the effectiveness of EMCTS in case of discrete action space, but how can EMCTS (or some of its adapted variants) handle the continuous action space? Moreover, how sensitive is EMCTS to the exploration hyperparameter \\beta?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jb55rHSkG8", "reviewer": "Reviewer_yivx", "summary": "This manuscript tries to solve an important issue in Monte Carlo Tree Search (MCTS), that MCTS doesn’t consider the propagation of the uncertainty of learned model. The authors proposed Epistemic Monte Carlo Tree Search (EMCTS), which can account for the epistemic uncertainty in search and harness the search for deep exploration. The proposed method is achieved in three steps: search with learned reward model, planning for exploration with epistemic search, and propagating epistemic uncertainty in search. EMCTS is evaluated in the challenging sparse-reward task of writing code in the Assembly language SUBLEQ and hard-exploration benchmark Deep Sea, and the results show that the proposed framework can solve the quiz faster than AlphaZero/Muzero.", "questions": "1.\tThis method assumes that the reward is independent when $i \\neq j$. Is this satisfied in programming or math task? for example, when $i = j+1$?\n2.\tHow to get the true transition model in typical tasks?\n3.\tIs accuracy and uncertainty of the learned model is dynamically improved in the learning procedure? And is this will affect the consistent assumption?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThis manuscript propose a novel and solid framework to introduce and deal with uncertainty of learned model caused by limited data or sparse reward environments, which is not taken into account in the standard MCTS.\n2.\tEMCTS solves the two-fold objective, i.e., extend MCTS to estimate and propagate the epistemic uncertainty from the uncertain learned model and harness the epistemic uncertainty in the search to achieve deep exploration of the environment, via formulating the epistemic uncertainty, and search based on the propagated UCB.\n3.\tBy giving some assumption, the estimation and propagation of the epistemic uncertainty is defined by a random variable and computed via the variance of reward.\n4.\tExperiments demonstrate that the proposed EMCTS can solve the harder task in a much smaller number of samples than AZ.", "weaknesses": "1.\tSome assumptions might make EMCTS inapplicable to real complex problems. They assume that the transition model P is true. Theorem 1 need $Q^{\\pi}$ to be linear. The learned models are assumed to be consistent. These is not reasonable in many cases.\n2.\tIn many cases, the transition models need to be estimated, and then the EMCTS will not work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P4FynaicR5", "reviewer": "Reviewer_v4iH", "summary": "The authors propose a novel method, Epistemic - Monte Carlo Tree Search (E-MCTS) which incorporates the uncertainty estimates into MCTS. The authors theoretically motivate their approach as well as provide an experimental study showing the benefit of using their method in hard exploration problems.", "questions": "See weaknesses for the questions.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is generally well-written (except for a few places), the proposed method is novel and the contribution is significant.\n\nMCTS is a technique which showed great results in relatively simple domains and it still remains a challenge to apply it in hard-to-explore domains. This work addresses this challenge by adding the uncertainty estimation mechanism into MCTS. The paper demonstrates good results in hard-to-explore domains.", "weaknesses": "1. In abstract, lines 14-15, it is written \"MCTS does not account for the propagation of this uncertainty however.\". At this point of the text, it is not clear what it means to propagate the uncertainty and why it is necessary. It might be worth adding a sentence about \"propagating uncertainty\" before that.\n\n2. The authors mention in many places that the model will be uncertain about the part of the state-action space which was not observed during training, like for example, lines 125-126 \"thus their predictions are uncertain outside of the training set\". But what about the situation when the model is actually **certain** about the unobserved part of the state-action space, but **wrong** ? I believe this situation is also likely to happen. There is no discussion of it at all in the paper.\n\n3. The authors propose to estimate the square root of the variance $\\sqrt{V[Q]}$ as $1/N \\sum_{i=1}^{N} \\sqrt{V[v]}$ (see, for example eq.11), but this is not how it generally is estimated. Instead, one should estimate  $\\sqrt{V[Q]} = \\sqrt{1/(N-1) \\sum_{i=1}^{N} (v_i - \\bar{v})^2}$, where $\\bar{v}$ is the empirical average of $v$. Where does this estimate come from? What is the impact of using this estimate rather than a more correct one which I wrote?\n\n4. The authors write \"models are consistent\" (line 269), but it is not clear what is meant by consistent. They also say in line 270, \"V[V[s]] ~V[Vpi[s]]\". It is unclear why this must be true. Also, the authors say \"Imposing again the assumption that the learned models are consistent\" (in lines 276-277). It is unclear what they mean by consistency. Suggestion -- write clearly (as an equaition) the definition of the consistency. Then, argue / discuss the implications of this assumption and why this assumption is true in the first place.\n\n5. In lines 388-390, the authors say \"achieve deep exploration\", what does it mean? From the experiments, I can only conclude that the method solves these specific tasks, but it is wrong to claim that it \"achieves deep exploration\", since first, this \"achieving\" is not defined and second, it is not implied from the experiments that it will hold in general.\n\n6. The authors evaluate their method in two domains. I think in order to increase the significance of their work, the authors should also evaluate on more easy-to-explore domains (i.e., in Atari) to show that their method works consistently well overall, as well as on more hard-to-explore domains (i.e., in Atari) to show that in situations where it should work well, it does it consistently. For example, would it also work well in domains like chess? Will the findings still hold? Will E-MCTS actually be more effective here compared to AZ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)