Trust, but verify: model-based exploration in sparse reward environments
Authors: Konrad Czechowski
Tomasz Odrzygóźdź
Michał Izworski
Marek Zbysiński
Łukasz Kuciński
Piotr Miłoś
Venue:  (2021)
Keywords: reinforcement learning
model-based
exploration
on-line planning
imperfect environment model

Abstract: We propose $\textit{trust-but-verify}$ (TBV) mechanism, a new method which uses model uncertainty estimates to guide  exploration. The mechanism augments graph search planning algorithms by the capacity to deal with learned model's imperfections. We identify certain type of frequent model errors, which we dub $\textit{false loops}$, and which are particularly dangerous for graph search algorithms in discrete environments. These errors impose falsely pessimistic expectations and thus hinder exploration. We confirm this experimentally and show that TBV can effectively alleviate them. TBV combined with MCTS or Best First Search forms an effective model-based reinforcement learning solution, which is able to robustly solve sparse reward problems. 

Under review as a conference paper at ICLR 2021
TRUST, BUT VERIFY: MODEL-BASED EXPLORATION IN SPARSE REWARD ENVIRONMENTS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose trust-but-verffy (TBV) mechanism, new method which uses model uncertainty estimates to guide exploration. The mechanism augments graph search planning algorithms with the capacity to deal with Iearned model's imperfections. We identify certain type of frequent model errors, which we dub false loops, and which are particularly dangerous for graph search algorithms in discrete environments. These errors impose falsely pessimistic expectations and thus hinder exploration. We confirm this experimentally and show that TBV can effectively alleviate them. TBV combined with MCTS or Best First Search forms effective model-basee reinforcement learning solution, which able to robustly solve sparse reward problems.
INTRODUCTION
Model-based approach to Reinforcement Learning (RL.) brings promise of data efficiency, and with it much greater generality. However, it is still largely an open question of how to make robust model-based RL algorithms. In most cases, the current solutions excel in low sample regime but underperform asymptotically, see WWan et al.] (2019); Nagabandi et al. (201 8ay; Kaiser et al. (2020). The principal issues are the imperfections of the learned model and fragile planners not able to robustly deal with these imperfections, see (Sutton & Barto 2018) Section 8.3), (François-Lavet et al.) 2018 Section 6.2), (Wang et al.) 2019. Section 4.5).
Model errors are unavoidable in any realistic RI scenario and thus need to be taken into account, particularly when planning is involved. They can be classified into two categories: optimistic and pessimistic, see (Sutton& & Barto 2018 Section 8.3). The former is rather benign or in some cases even beneficial, as it can boost exploration by sending the agent into falsely attractive areas. It has self-correcting mechanism, since the newly collected data will improve the model. In contrast, when the model has a pessimistic view on a state, the agent might never have the incentive to visit it, and consequently, to make the appropriate adjustments. In this work, propose trust-but-veriy (TBV) mechanism, à new method to augment planners with capacity to prioritise visits in states for which the model is suspected to be pessimistic. The method is based on uncertainty estimates, is agnostic to the planner choice, and is rooted in the statistical hypothesis testing framework.
Taking advantage of the graph structure of the underlying problem might be beneficial during planning but also makes it more vulnerable to model errors. We argue that graph search planners might benefit most from utilising TBV. While TBV can correct for any type of pessimist errors, we explicitly identify certain type of model errors which frequently occur in discrete environments, which we dub false loops. In a nutshell, these are situations when the model falsely equates two states. Such errors are much similar to (Sutton & Barto] 2018, Example 8.3), in which the model erroneously imagine "bouncing off' of a non-existing wall and thus failing to exploit a shortcut.
From a more general point of view, the problem is another incarnation of the exploration-exploitaiion dilemma. We highlight this by evaluating our method sparse reward environments. In planning context, exploration aims to collect data for improving the model, while exploitation aims to act optimally with respect to the current one. The problem might be solved by encouraging to revisit state-action pairs with an incentive of "bonus rewards' based on the state-action visitation frequency. Such a solution, (Sutton & Barto 2018 Dyna-Q++ is restricted to tabular cases. TBV can be though as its scalable version.

---

Under review as a conference paper at ICLR 2021
Our contributions are:
TBV a general risk-aware mechanism of dealing with pessimistic model errors, rooted in the statistical hypothesis learning framework.
Conceptual sources and types of model errors accompanied with empirical evidence.
Practical implementation of TBV with: classical Best First Search a classical graph search algorithm family and Monte Carlo Tree Search the state-of-the-art class of planners in many challenging domains.
Empirical verification of TBV behaviour in two sparse rewards domains: ToyMontezumaRe- venge RRoerric et al. (2018) and the Tower of Hanoi puzzle.
The code of our work TrustButVerify
available at:
RELATED WORK
There is huge body of work concerning exploration. Fundamental results in this
from the multi-arm bandits theory, including the celebrated UCB algorithm (Auer et al. (2002)) or Thompson sampling [Thompson] (1333). ), see also Lastimoe Szepesvári (2020) for thorough treatment of the subject. There are multiple variants of UCB, some of which are relevant to this work, including UCB-V V Audibert et al. (2007) and tree planning adaptations, such as UCT (Kocsis et al. (2006)) or PUCT (Silver et al. (2017 (018))) Classical approach to exploration in the reinforcement learning setting, including the principle of optimism the face uncertainty and e-greedy exploration, can be found in Sutton & Barto (2018). Exploration in the form of entropy-based regularization can be found in A3C Mnih et (201))) and SAC (Haarnoja et al. (2018) ). Plappert et al.) (2017) > and Fortunato et al. (0117) introduce noise in the parameter space of policies, which Icads to state-dependent exploration. There are multiple approaches relying on reward exploration bonuses, which take into account: prediction error (Stadie et al. (2015), (Schiidhuber (2010) Pathak et al. (2019). [Brrda et al. (2018), ) visit count (Bellemare et al. (2016), Ostrovski et al. (2017), ). temporal distance (Machado
al. 2020). ). classification (Fu al. (2017)) )) or information gain (Sun et al. (20TT), Houthooft
et al. 2016)). An ensemble- masemble-based reinforcemee learning counterpart of Thompson sampling can be found in Osband et al. al.| (2016) and Osband al. (2019). An exploration driven by experience-driven goal generation can be found in Andrychowicz et al. (2017). A set of exploration methods has been developed in an attempt to solve notoriously hard Montezuma's Revenge, see for example Ecoffet et al. (2019); Guo et al. (2019). In the context of model-based planning Lowrey et al. (2019) and Milos et al. (2019) use value function ensembles and uncertainty aware exploration bonuses (log-sum-exp and majority vote, respectively).
More recently, Pathak et al. (2017), Shyam et al. (2019), Henaff (2019) and Sekar et al. (2020) dealt with exploration and model learning. These works similar in spirit to ours. They train exploration policies intending to reduce the model error (c.g. by maximizing the disagreement measure). Our work differs from the above in the following ways. First, we aim to powerful graph search techniques as planners simultaneously to learning of the model. Our method addresses the fundamental issue, which is balancing intrinsic planner errors and the ones stemming from model imperfection. Second, we use the prediction error of the model ensemble to measure model uncertainty and apply statistical hypothesis testing framework switch between actions suggested by the model and actions leading to model improvement. Third, we use a discrete model and a discrete online planning regime.
When learned model is unrolled during planning, errors typically accumulate dramatically. Numer of works adress this problem. |Racaniere et al., (2017) and Guez et al. (2018) are two approaches to learn the planning mechanism and make it robust to model errors. In somewhat similar spirit, Eysenbach et al. (2019) treats the replay buffer as a non-parametric model forming a graph and uses ensembles of learned distances as a risk-aware mechanism to avoid certain types of model errors. Nagabandi et al. (2018b) successfully blends the strengths of model-based and model-fi freee approaches. PlaNet (Hafner et al. (2019) and Dreamer Hafner et al. (2020) train latent models, which are used for planning. Conceptually, a similar route was explored in MuZero (Schrittwieser et al. (2019) and Universal Planning Networks (Srinivas et al. (011)). Farquhar et al. (201)) and Oh et al.
2

---

Under review as a conference paper at ICLR 2021
(2017) investigate the possibility of creating neural network architectures inspired by the planning algorithms.
Many model-based reinforcement learning algorithms, including ours, follow the general framework laid out in Dyna, see Sutton (1991). ). Kaiser et al. (2020) uses a model to collect fictitious playouts and obtains impressive results for low data regime on Atari. In the continuous domains, similar approach is adopted by Kurutach et al. (0188. Simultaneous training of a single policy on model ensemble is proposed tackle model errors. Interestingly, this approach is reported perform better than paok-propagttion through time. Clavera et al. (2018) indicates that polices trained on model ensembles might be weeeeevnsevvttvve and proposed to use policy meta-learning. Another approach to dealing with model errors works by choosing the unroll horizon for a model. Janner al. (019)), proposed short model--generater branched rollouts starting from data collected on "real environment". Perhaps surprisingly. they find that one-step rollouts provide competitive results. Similarly, short rollouts are used in Feinberg et al. (2018) and [Buckman et al. (2018) to improve value estimates. [Janerr et al. (2019); Buckman et al. (2018) uses ensembles to reduce model bias. The former generates diverse data similarly Chua et al.] (2018). and the latter automatically adapt the planning horizon based on uncertainty estimates, Xiao al. (2019) proposed another adaptive horizon mechanism based on measurement of model errors using principled Temporal Difference methods.
There is a huge body of work about planning; for classical results, the interested reader is referred to Cormmen al. (2009), Russell & Norvig (003) and the references therein. Traditional heuristic algorithms such as A Harr et al. 1968)) or GBFS (Doran & Michie (1966)) are widely used in practice. In/Agostinelli et al. (2019) the authors utilise the value-function improve upon the A" algorithm and solve Rubik's cube. Similarly, Orseau et al. (2018) bases on the classical BFS to build heuristic search mechanism with theoretical guarantees. The Monte Carlo Tree Search (MCTS) algorithm, which combines heuristic search with learning, led to breakthroughs in the field, see Browne et al. (2012) for an extensive survey. Famously, [Silver et al. (2018) develop MCTSSbasee technique to master the ancient game of go. The POLO algorithm presented in Lowrey et al. (2019) proposes to enrich MPC planning with ensemble-base risk measures to augment exploration. This work is extended by NEEDLE (Milos et al. (2019)) to tree-based MCTS planners and by Lu et al.
(2019) to successfully tackle life-long learning scenarios of environmental change. Hamrick et al. (2020) explores how use better statisties collected while searching to calculate signal for value tunction training.
3 TBV FRAMEWORK
This work attempts to pave the way in harnessing the power of graph search methods to reinforce model-based re- inforcement learning. Majority of the planners were designed to solve well defined problem, which means that the user is expected to supply perfect model. Consequently, when the user fails to do it, the planner can yield an unexpected, or outright wrong, result. Although in some environments, like games or simulators, a perfect model available, in most real- wollw sce- narios it is luxury we cannot afford. Especially in the learning regimes, ob- taining the perfect model requires ex- ploration of the whole state space, which is usually unacceptably hard. Consequently, any real-world model- based RI. system is unlikely to avoid dealing with model errors.
False-loop visualization
Agent's current state
What agent thinks would happen
What would actually happen
L
Room position: (1. 5)
Room position: (1, S)
Room position: (1,
Agent position:
Agent position:
Agent position:
Figure 1: Agent (gray circle) is moving in grid-world. can move through the door (blue) to other rooms, it enter trap (red) the episode terminated. (Genuine) one-step loop arise when agent attempts to walk into the wall. In the example, the model imagines that performing action "right" will not result in environment change (false loop). In fact choosing this action would result in moving to the next room.
3

---

Under review as a conference paper at ICLR 2021
We thus led to two seemingly conflicting desiderata for the choice of method: would like to use planners which are robust to model errors, and planners which leverage the structure of the underlying problem, and hence more susceptible to model emror. We advocate developing methods, which will facilitate adoption of search algorithms into setting with imperfect models. In this work make step towards implementing this plan. We identify and study certain type of model errors, which we dub false loops, and we propose Trust, but verify (TBV) method, which can successfully immunize planners with respect to said errors.
3.1 MODEL ERRORS
Sutton & Barto 2018 Section 8.3) conveniently categorize model errors into two categories: opti- mistic and pessimistic. situation when a model predicts higher reward or better state transitions (optimistic error) is easier to handle since while the agent enters erroneous region, it collects corrective data. More dangerously, predictions more pessimistic then reality may prevent the agent ever to visit certain regions.
The optimistic and pessimistic errors are often of the same nature. In this work, we concentrate on errors related the graph structure the problem. By definition, the edges in this graph correspond to transition induced by actions, and thus the errors are "incorrect edges". Perhaps the simplest prediction task (for a model) change or not the current state). Another task is the prediction of absorbing states. In this work, we focused on the loop errors, as they turn out be critical to performance (see F examples). In experiments, we also observed other types of errors (like "random teleports">, however they disappeared rather quickly during the training. It is possible that they would be more problematic in other environments, which leave for further work. In Figure 5 show numerical results that show rather frequent occurrence of false loop. This is a pessimistic error, which, unless corrected, c.g. by TBV, prevents exploration.
determine if an edge is one-step loop (i.e. if an action will
Algorithm 1 bosel-based training loop
# Initialize parameters of ensemble of models Initialize parameters planner specific networks Initialize fer
repeat
episode +- COULLEC_EEPISODE
B fer.ffrreBACC
Train ensembles of models
Update planner specific networks
until convergence
function COLLECT
SOLLECTTEPISSDE EPISODE
EES.RESET
episode +-
repeat
Q f TBV Clanser ACTION(S)
TB V-augmmentee graph planner using models, see Algorithm
ENV.STEP(a)
Appisode.APPEND((ss....
until episode is done return episode
3.2 STATISTICAL HYPOTHESSI TESTING
STATE_ SCORE(s) scoring each state by the model's uncertainty. Consider a state and denote the set of states reachable from in specified budget of steps, by D(s). In this paper, we will take D(s) as a search graph expanded by the planner starting from s and standard deviation of model ensemble prediction eπrоr for STATE SCORE, STATE_SCORE, however other options are possible (c.g. states achievable by a behavior policy or information gain, respectively). The set (s), together with STATF_ SCOR__ imply the distribution of values of STATE_ SCORE for the set
Assume that there exists a function STATE
4

---

Under review as a conference paper at ICLR 2021
reachable form We are interested in determining whether the actions recommended by the planner at state s leads to good exploration choices both in terms of the model (state-space exploration) and the value function (proper data for value function learning). To do this, make use of statistical hypothesis testing. Namely, we form a null hy hypothesis, stating that the planner is exploring correctly, and an alternative hypothesis, making opposite claim. If the STATE STATE_SCORE(() SCORE(()) takes extreme values, then it provides evidence against the null hypothesis. Hence, as a critical value for the test, we take the quantile of the STATE_ STATE distribution on (s)). This procedure has several interesting properties. It is invariant to the SCOTE_ scale, provides an automatic method for threshold selection, and introduces only one task-agnostic hyperparameter. It can also mitigate the negative effect of propagating the errors in value function, which can deteriorate learning (see Lee et al. (2020) and Kumar et al. (2020)). Finally, since hypothesis testing closely related to confidence intervals, our approach fits nicely with confidence bounds exploration methods.
3.3 TRUST, BUT VERIFY METHOD
Trust, but verify (TBV) is a method which can be integrated with graph search planners. The key idea of TBV is to prioritize visits in states for which the model is suspected to be pessimistic. In each state, the planner is asked for a recommended action. If the model uncertainty of the current state is high, we may suspect that the planner's s results are misleading. We quantify by an appropriate statistical test described in Section 3.2 This promotes exploration and thus reduces errors in the model. To measure uncertainty, we utilize ensembles, which empirically proved to be successful that regard (see e.g. Osband et al. (2018). The details follow the pseudo-code for TBV. listed in Algorithm 2 For completeness, we also present a typical model-based training loop in Algorithm I
As shown in Algorithm 2 TBV interacts with planner, which uses imperfect learned model. During its execution, the planner expands a search graph, 9p. in order to propose an action ap. Each state-action pair in 9p is given a score reflecting uncertainty assigned to it by the model, and which is quantified by a function DISAGREEMENT MEASURE. Based on that, TBV decides whether to keep the planner's decision op (trust the model) or override it (and explore to verify model predictions). More precisely, a state-action pair with the maximal score is considered if it reaches above the threshold given by quantile_st _score. We found using quantiles instrumental in avoiding tuning thresholds which are problem-specifee and change during the training.
Furthermore, QR is relatively easy to tune (see Section 4 and is the only hyperparameter introduced by TBV. In the algorithm, we use additional randomization to prevent multiple revisits of the same iattonaction pair, while waiting for the model (and scores) update (see Section A.5 in Appendix for more detailed discussion). This could be alternatively realized by more principled approach, which we leave for future work.
Using TBV yields little computational overhead beyond the necessity of using ensembles (in efficient implementations STATF_ and TRANSITION TRANSITION_SCORE s_sCss calls can be inlined into planner. CCHOOE_AATTOOEE tation; in our experiments, we found standard deviation computed on states to work well. Other methods, like Bayesian inference, could also be used.
MEEEEEE DISAGREEMENT MEASURE depends on the state space represen-
3.4 BEST FIRST SEARCH
Best First Search (BestFS) is a family of search algorithms that build a graph by expanding the most promising unexpanded node. the off-line setting, the search is run upon reaching the goal state. In order to apply BestF'S in on-line framework, during each planning phase, we choose to extend the graph by a fixed amount of nodes, typically 10. Afterwards, the recommended action is the first edge on the shortest path to the best node in the subgraph searched so far.
An important design decision choosing heuristics for assigning nodes numerical values. This leads to many well-known algorithms (e.g., BFS, DFS, A etc.). In our experiments, concentrated on exploration and thus used Di sagreement, Becnntt_eassuuu Measure (standard deviation) between ensemble predictions. This choice proved to be effective in discrete problems with sparse rewards.
By design, BestFS ignores one step loops and thus is especially prone to false loops described in Section
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 TBV planner
Require:
model planner
ensemble of models used in Algorithm
planner that uses model
QR QUANTILE(1 4) RANDOM()
quantile rank (0, 1)
Use:
computes the q-quantile of list I
random number from (( 1)
function CHOOSE_ACTION(state)
ap - pww.meerccHOOSE
(tate)
9p <
PLANNINNG
scores [
for state 9p do
CROFS.NPENDD(TTTTE_SOOEE (slaas) quantile_score +- QUANTILE(SCOres, QR) one_step_score - for E actions do tne_step_scom APEND CeATCIISSNNOOOESttteCCCCC a))
if maxx(nne_ste sccorss > quantile_ score and RANDOM() > 0.5 then
return arg action one one_slep_scom else
return
function TRANSITION SewrrrION_ScRRsttttete.. action)
predictions +
for network E model do
nerl_slate next soeul_rewarddee <- BEA.://KPPPEEIIINEEETTETCCSC SEXT_STATE(state, action)
Predictions.APPENDD( (wwerlleeeeeee state, nealrreward))
return DISAGREFMENT_MEE MAA.EEEEMNNNLMAASSSSERrrrdrdrSS
function STATE_SCORE(staate
return maXaction hTt.aaaooo.c.aaa.ooooooooooott..
3.5 MONTE CARLO TREE SEARCH
Monte Carlo Tree Search (MCTS) is well-established planning algorithm which was successfully applied to complex problems. Due to simplicity and effectiveness, has numerous extensions (see
Browne et al. (0122) for a comprehensive review) including famous AlphaZero (Silver et al. (2018)).
vanilla MCTS constructs search tree in four stages: node selection, leaf expansion, rollout, and backpropagation (see Browne al. (2012) Section 3.1)). In modern approaches, the rollout phase is often replaced by neural network evaluation step. MCTS often equipped with auxiliary mecha- nisms exploiting the graph structure of the problem. In our work, we use MCTS implementation with four such mechanisms: hard loop-avoidance inside the search tree, soft loop-avoidance within the whole episode, transposition tables and amortized value estimates, see Milos al. (2019) for details.
Transposition tables (Childs al. 2008 Gelly et al.) 2012) enable sharing information between different tree nodes, which correspond to the same state (i.e. have been reached using distinct trajectories). Similar in spirit mechanisms, which attempt avoid visiting node multiple times. These are akin to classical graph search methods in which a node it typically visited only once. This may take place on the level of the whole episode or within one planning phase (in the search tree). A "soft" way of implementing such mechanisms is to use "virtual loss", which assigns temporary negative value when a graph node is first encountered. This encourages the exploration and tree building mechanism to avoid this node. Such solutions have been proposed in (Segall (2010) to enhance parallelism and later used (McAleer et al. 2019) to tackle Rubik's cube search. hard version (equivalent to setting virtual loss to co) strictly prohibits entering the same node twice. It Milos et al. 2019) it reported to be a significant efficiency boost for modest planning budgets on the classical Sokoban puzzle. Recent works (c.g. Milos al. (2019), Hamrick al. (2020)). propose to utilize "amortized value estimates" (which are calculated using the internal MCTS statistics) as targets for value function for training.

---

Under review as a conference paper at ICLR 2021
Our version uses learned value function (similarly to AlphaZero) to evaluate new nodes. Similarly to Lowrey et al. (2019) and MMilos et al. (2019) we use also value function ensemble to ensure exploration during planning.
EXPERIMENTS
The experiments below were designed to illustrate the aforementioned false loops model errors. They also demonstrate the effectiveness of TBV.
We have selected Toy.oonizzuaRRevenge envi- ronment and the Tower of Hanoi puzzle (with 7 dises). These environments are challenging for RL as they have sparse rewards, and require least a few hundred steps to reach the solution. At the same time, they are solvable through an exhaustive search using graph search algorithms with access to a perfect model. Since there is gap in the performance of these two categories of methods, the environments present good testing grounds for studying the unfavorable influence of model errors on graph planners.
G
Figure Map of ToyMonnezumaRevenge state space. The only reward is given after reaching the goal room marked with G. To obtain agent needs to gather several keys (marked in yellow) and go through doors (marked in blue). Step- ping on trap (marked in red) results in episode termination.
As for performance metrics, we use minimal dis- tance to the goal. It is measured in steps and treated as a function of total environment steps used in training. We apply this measure two planners: BestFS and MCTS (each in three versions: with TBV, with e-greedy and without additional exploration mechanism). As additional baseline, we also use RND (see Burda et al. (208)), ) a strong model-free exploration algorithm.
In all experiments, we found that using TBV mechanism significantly outperform other baselines.
4.1 TOYMONTEZUMAREVENT
Revee is navigation, maze-like, environment introduced by Roderick al. 20118 a testing ground for long-horizon planning and exploration (see Figure 2 It has greatly simplified visual layer when compared the original Montezuma's Revenge Atari game, but retains much of its exploration difficulty. In our experiments, we consider the biggest map containing 24 rooms and sparse rewards: the agent gets reward 1 only if reaches the treasure room; otherwise the episode is terminated after 600 steps. Observation is represented room location, agent position within the room, and status of all keys and doors on the board, see Figure 2 for the full map of the state space.
tuple containing current
For both planners, MCTS and BestFS, using e-greedy improves over baseline version, but not as much as TBV (see Figure 3).
turns out that traps (see the caption below Figure [ pose a challenge for BestFS algorithm. order to mitigate this issue, modified the TBV mechanism for BestFS in this environment to explicitly avoid traps (performing actions resulting in episode termination without positive reward, according to the learned model). For a fair comparison, we also added the same mechanism e-greedy variant: when sampling from the action space, only the actions not leading to traps were considered. Similar improvements were unnecessary for MCTS.
For BestFS, 4 out of 10 experiments were unable to leave the first room. This stemmed from the fact that the agent could not make progress: it kept getting stuck in the early stages of exploration due to the inability to pass through false loops. This is visualized in Figure 5 where it is shown that TBV encourages the agent to leave the first room when it has chance do so but is being blocked by the model error.
We use the code from httptt/g//////thhb....m////ggggg

---

Under review as a conference paper at ICLR 2021
Interestingly, it was quite hard to tune RND on this domain (the agent struggled to find the second key and explored at most 14 out of 24 rooms). This could be related to the fact that RND needs a lot of data (originally RND was trained with billions of transitions), whereas experiments are conducted in low data regime. Hyperparameters choice for RND can be found in Appendix (see Table T Table and Table
reled VCTS T5V
Mameere cxpe.
Fummor of expee
Figure 3: ToyMoonezumaRReengee, comparison between planners augmented with TBV, e-greedy, and top-level exploration mechanism. Results are averaged over 10 random seeds, shaded areas show 95% confidence intervals.
15.2
Figure 4: Tower of Hanoi, both MCTS and BestFS quickly find the solution if augmented with TBV. Other methods struggle to find solution. Results are averaged over 10 random seeds, shaded areas show 95% confidence intervals.
Mmw
62-
Figure 5: Numerical measurement of influence of TBV on BestFS in the presence of false loop in ToyMR. The upper (blue) line presents the frequency of reaching the open doors in the first room for the agent without TBV. This agent never enters the door due a false loop error. The lower (orange) line present the frequency the agent would leave the room if TBV was used.
Figure 6: False loop verification in the Tower of Hanoi. We consider two agents: MCTS with TBV (orange) and e-greedy (blue) exploration (presented also on Figure 4 The plots shows how often agent performed action which falsely seemed to be a loop in the state-action graph. TBV V does much better job in verifying such tran- sitions.
4.2 TOWER OF HANOI
The Tower of Hanoi is classical puzzle consisting of 3 pegs and disks (see Figure 7 The objective of the game is to move the entire stack of disks from the starting peg to the goal peg. The rules that only one disk can be moved at time and it is not allowed to put larger disk on top of smaller one. It can be shown that an optimal solution requires 2n 1 moves (see e.g. Pierrot et al. (2019)). This makes it challenging combinatorial problem and interesting domain for planning
8

---

Under review as a conference paper at ICLR 2021
methods. Model-free algorithms struggle to deal with larger instances (Truussard et al. (2020) used n = 4, Edwardds et al. (2018) used n = 3). In this paper, we use a considerably harder version, with n = 7. The observation passed to the agent is represented as binary vector of length x Each consecutive triplets of bits encode the location (peg) of a given disk. This representation makes the task more difficult for the environment model
do not pass disk sizes. This prevents easy generalization of the dynamics of the environment from partial data, and it makes it challenging to learn the rule that "the smaller disk can always be placed on larger". Instead, the agent needs to learn the relation between sizes for each pair of disks separately, as the exploration progresses.
As can be seen in Figure TBV method signifi- cantly improves both MCTS and BestFS planners in this domain. This is due to the nature of the Tower of Hanoi, which in the early stages of train- ing creates an illusion that the larger disks stays in the same position. It may result in the false belief of the model that the larger disks cannot be moved, hence causing the false loop errors. We verified that TBV handles such errors effectively, Figure 6 We found that RND continued explore the environment when left for longer train- ing (up to 25M transitions, see Figure 10 in the Appendix.). Its progress is, however, very slow when compared other methods. This in line with our observation from the previous section that RND is designed to work on larger scale ex- periments.
False-loop visualization
Agent's cument
What agent thinks would happen
actualy happen
4.3 QUANTILE RANK SENSITIVITY
By design, TBV it quite easy to tune. Its only hyperparameter is Quantile Rank (QR). We found out that values in the range 0.8 - 0.95 worked well across most choices of environments and planners. Excessively large value of QR (e.g. 0.99) causes TBV to accept planner's actions too often, slow- ing down exploration. Performance of BestFS agent with 7BV across multiple values of QR is presented in Appendix in Figure g
Figure 7: Tower of Hanoi puzzle. For the first time, the agent finds himself in a position to move the fourth disk but mistakenly believes that is not possible, resulting false-loop.
5 CONCLUSIONS
This work concentrates on an important open research problem, concerning the design of planners, which are resistant to model errors. Our study shows that model imperfections, especially false loops, can significantly hinder exploration. New algorithm presented in this paper, TBV, alleviates them by repeatedly verifying model predictions. TBV builds upon a statistical hypothesis testing framework and uses disagreement measure distribution form an appropriate test.
Based on experiments in two challenging domains, we verify the design to be successful. Precisely, we show experimentally, that augmenting planner with TBV, significantly improves agents exploration. At the same time we empirically confirm that TBV actively encourages the agent to pass through false loops.
Finally, TBV is a robust algorithm: it can be combined with different model-based planners and is easy to tune.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the ru- bik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8): 356-363, 2019.
doi: 10. 10.1038//4256--19-000000 URL https:://ol..rgg 10338
142256-0199
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welin- der, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojeiech Zaremba. Hindsight ex- perience replay. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 5048-5000 5058, 2017. URL http::/paas: wwappprs.niii... cc/paper///ppppcpppppcp..c....ee 1e000--innngggtttee-ppeee eepereeeeeeeeeeeeeppaaaaa
Jean- Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International conference on algorithmic learning theory, pp. 150-165, Springer, 2007.
Peter Auer, Nicolo Cesa- DisacBianchh,, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-2555 2002.
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos.
Unifying count-based exploration and intrinsic motivation. Advances in neural information processing systems, 19:1471-1479) 2016.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlishagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
Jacob Buckman, Danijar Hafner, George Tucker, Eugene Brevdo, and Honglak Lee. Sample- efficient reinforcement learning with stochastic ensemble value expansion. In Advances Neural Information Processing Systems, pp. 8224-8234, 2018.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov, Exploration by random network distillation. CoRR, abs/1810. 12894, 2018. URL http::tppppa....o/////oo// 1bt..bb..11..1144 12894
Benjamin E. Childs, James H. Brodeur, and Levente Kocsis. Transpositions and move groups in monte carlo tree search. In Proceedings of the 2008 IEEE Symposium Computational Intelligence and Games, CIG 2009, Perth, Australia, 15-18 December, 2008, pp. 389-395, 2008. doi: 10. 109/ CIG.2008.5035660
htt.://crr/1...11111..... htthttts:: /tt.tppp://oo.... wtt..o.rg111.. 1109//11001CCCC 2008 5035667036
Kurtland Chua, Roberto Calandra, Rowan McAllister and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. In NeurIPS 2018, pp. 4759- 4770, 2018
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Picter Abbeel. Model-based reinforcement learning via meta-policy optimization. 2nd Anmual Conference on Robot Learning, CoRL 2018, Zürich, Switzerland, 29-31 October 2018, Proceedings, volume 87 of Proceedings of Machine Learning Research, pp. 617-629. PMLR, 2018. URL http://
procceedi ngs mlmmlrr. pwwrss/v87... Laaeralll 8a. html
Thomas Cormen, Charles Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
James E Doran and Donald Michie. Experiments with the graph traverser program. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 294(1437):235-2) 1966.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go-explore: a new approach for expl-oxpoo problems. CoRR, abs/1901.10095, 2019. URL http:
7/ Tarxivv. www.ivv.rgaaab//aeae 901 10995
10

---

Under review as a conference paper at ICLR 2021
Ashley D Edwards, Laura Downs, and James C Davidson. forward-backward reinforcement learning. arXiv preprint arXiv: 1.t.::8803.1022,, 2018.
Ben Eysenbach, Ruslan Salakhutdinov, and Sergey Levine. Search the replay buffer: Bridging planning and reinforcement learning. In Hamna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc. Emily B. Fox. and Roman Gamett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 Decemher 2019, Vancouver, BC, Canada, pp. 15220- 15231, 2019.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treeqn and atreec: Differentiable tree planning for deep reinforcement learning. CoRR, abs/1710.11417, 2017.
Vladimir Feinberg, Alvin Wan, Ion Stoica, Michael Jordan, Joseph Gonzalez, and Sergey Levine. Model-based value estimation for efficient model-firee reinforcement learning. CoRR, abs/1803.00101, 2018. URL
abw.g//.a///10...o.o. 00101
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et Noisy networks for exploration. arXiv preprint arXiv: I 700.7 10295, 2017.
Vincent François-Lavet Peter Henderson, Riashat Islam, Mare G. Bellemare, and Joelle Pineau. An introduction to deep reinforcement learning. Found. Trends Mach. Learn., 11(34))211-33 2018. doi: 10. 00.11/2000000771 URRLhttps::/ddt org/ 1011/120011110000000
Justin Fu, John Co-Reyes, and Sergey Levine. Ex2: Exploration with exemplar models for deep reinforcement learning. In Advances in neural information processing systems, pp. 2577-2587, 2017.
Sylvain Gelly, Levente Kocsis, Mare Schoenauer, Michèle Sebag, David Silver, Csaba Szepesvári. and Olivier Teytaud. The grand challenge of computer go: Monte carlo tree search and extensions. Commun. ACM, 5563) 2012. doi: 01114/2209358.209333777 URL https: doii
org/10 1ttp/00.111/200950 000.9993888.2299339 2093574
Arthur Guez, Theophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Rémi Munos, and David Silver. Learning to search with MCTSnets. In ICML, 2018.
Yijie Guo, Jongwook Choi, Marein Moczulski, Samy Bengio, Mohammad Norouzi, and Honglak Lee. Efficient exploration with self-imitation learning via trajectoryy policy. CoRR, abs/1907.10247,, 2019. URL http: owg. abs wwwp//////..m 10247
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maxi- mum entropy deep reinforcement learning with stochastic actor. arXiv preprint 1801 .91290 2018.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference on Machine Learning, pp.
PMLR, 2019.
Danijar Hafner, Timothy P. Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to con- trol: Learning behaviors by latent imagination. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL /tt.tppsss//ppeeeeiiee htt.://www..ee.oommm.aaaao......
Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter W. Battaglia. Combining q- g-learning and search with amortized value estimates. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL htttts:://ppereeeestsss SkeAaJrKDS
net forum?? d
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
11

---

Under review as a conference paper at ICLR 2021
Mikael Henaff. Explicit explore-exploit algorithms in continuous state spaces. In Advances in Neural Information Processing Systems, pp. 9377-992 79877 2019.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, pp. 1 1109-1112 1117, 2016.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-bused policy optimization. In Advances in Neural Information Processing Systems, pp. 12519-12530,
2019.
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Afroz Mohiuddin, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model based reinforcement learning for atari. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa. Ethiopia, April 20-30. 2020. OpenReview.net, 2020. URL https: /ttp://///pppeeeeeeeeeee net. Forum?id Swccs
Levente Koesis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006.
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforcement
learning via distribution correction. arXiv preprint arXiv:2003.07335, 2020.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings. OpenReview.net, 2018. URL. URL. http:tttt//// http:///ppeeevveeeeeeeeee www.//etturmma/. wtwfoorrmmdddJJiiiiii... d=s.jii nbWRZ,
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. arXiv preprint arXiv:2007. 04938. 2020.
Kendall Lowrey, Aravind Rajeswaran, Sham M. Kakade, Emanuel Todorov, and Igor Mordatch. Plan online, learn offline: Efficient learning and exploration via model-based control. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019. URL/Ettps://opezeeeiee http:/ewweee/oooooeeeeeeee Bieeeeii-BByyyyyee 7n05FQ
Kevin Lu, Igor Mordatch, and Pieter Abbeel. Adaptive online planning for continual lifelong learning. CoRR, abs/1912.01188. 188, 2019. URL
hawpg//bb//1992 01188
Marlos C Machado, Mare G Bellemare. and Michael Bowling. Count-based exploration with the successor representation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5125-5133, 2020.
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the rubik's 's cube with approximate policy iteration. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. URL htttps://oeereeviiit
net
Piotr Milos, Lukasz Kucinski, Konrad Czechowski, Piotr Kozakowski, and Maciej Klimek. Uneerttintt--eensiivvee learning and planning with ensembles. CoRR, abs/1912.09996, 2019, URL
http:://arxiv.org/eee
09996
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver. and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937, 2016.
Anusha Nagabandi, Gregory Kahn, Ronald S. Fearing, and Sergey Levine Neural network dy- namics for model- based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE International Conference Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pp. 7559-75666 IEEE, 2018a. doi: 10. N0.1109/CCRA.201....4.. 84631899 URL httpss:/ddo www.or//............. 20 8463189
12

---

Under review as a conference paper at ICLR 2021
Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dy- namics for model-based deep reinforcement learning with model-free fine-tuning, In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7559-7566. IEEE, 2018b.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio. Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017. Long Beach, CA, USA, pp. 6128-6128 2017. URL httthtttppppperre ni cc/paper/ 7192-va ue- pred et on-ionnttoorr
Laurent Orseau, Levi Lelis, Tor Lattimore, and Theophane Weber. Single-agent policy tree search with guarantees. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December
2018, Montréal, Canada., pp. 3205-3215, 2018. URL http::tpp////mm.ccmm htttttttspppppprrssssppesssp http//papprrssneee nips. cc/paper//p/pppc 7582 single agent powicyollllooooooloooooolleoeoeo tree- search with guarantees
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29:4026-4034, 2016.
Ian Osband, John Aslamides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. NeurIPS, 2018.
Ian Osband, Benjamin Van Roy, Daniel J. Russo, and Zheng Wen. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20:124:1-124:6,, 2019. URL http://jmlr.org
Saapers/v20/88-339 html
Georg Ostrovski, Mare G Bellemare, Aaron van den Oord, and Rémi Munos. Count-based exploration with neural density models. arXiv preprint arXiv: 1703.01310, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 2778-27778 PMLR, 2017. URL BtpL::ttpp/pprpceeeiiire http://rroceeennnooommmmeeeee/// mw...prrss/v70/ppaaak....
mlr.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. arXiv preprint 1tXiv:1906.04166 2019.
Thomas Pierrot, Guillaume Ligner. Scott Reed, Olivier Sigaud, Nicolas Perrin, Alexandre Laterre, David Kas, Karim Beguir, and Nando de Freitas. Learning compositional neural programs with recursive tree search and planning. In NeurlPS, 2019.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. arXiv preprint arXiv: 770.00195, 2017.
Sébastien Racanière, Theophane Weber, David P. Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomènech Badia, Oriol Vinyals, Nicolas Heess, Yujia Li, Razvan Pascanu, Peter Battaglia, Demis Hassabis, David Silver, and Daan Wierstra. Imagination- augmented agents for deep reinforcement learning. In NIPS, 2017.
Melrose Roderick, Christopher Grimm, and Stefanie Tellex. Deep abstract q-networks. In Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 131-138, 2018. URL http:htp::eee acm. org/ citations cfmii 0oeaa-337740 3237409
Stuart Russell and Peter Norvig. Artificial intelligence - a modern approach, 2nd Edition. Prentice
Hall series in artificial intelligence. Prentice Hall, 2003. ISBN 0130803022.
URL https
/ www. www.woollcctt. wttp:/oooo/ooo//////////
Jürgen Schmidhuber. Formal theory creativity, fun, and intrinsic motivation (1990-2010). IEEE
Transactions Autonomous Mental Development, 2(3):230-247, 2010.
13

---

Under review as a conference paper at ICLR 2021
Julian Schrittwiseer, loannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel. Timothy P. Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. CoRR. abs/191 1. .08265, 2019. URL htt.httt::/ttttt....
org/ abs/ /1ss/19 9911. 08265
Richard B. Segal. On the scalability of parallel UCT. In Computers and Games 7th International Conference. CG 2010, Kanazawa, Japan. September 24-26. 2010, Revised Selected Papers, pp. 36 47, 2010. doi: 10. (0.1007/978-3--44-119927 978 3- 0222-7428--2-2
4. URL
1007/
Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via sulf-super world models. CoRR, has/2005500560, 2020. URL
http:s//azxx..orrr//////000. 05960
Pranav Shyam, Wojciech Jaškowski, and Faustino Gomez. Model-based active exploration. In International Conference Machine Learning, pp. 5779-5788. PMLR, 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap. Fan Hui, Laurent Sifre, George Van Den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 2017.
David Silver, Thomas Hubert, Julian Schritwwesser, Ioannis Antonoglou, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 1144: 1144:1140-114: 2018.
Aravind Srinivas, Allan Jabri, Picter Abbeel, Sergey Levine, and Chelsea Finn. Universal planning networks. CoRR, abs/ hat//1804.00445. 2018. URL
http://vvwrg//bb///iaoaa 00645
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint 1507.00110 2015.
Yi Sun, Faustino Gomez, and Jürgen Schmidhuber. Planning to be surprised: Optimal bayesian ex- ploration in dynamic environments. In International Conference Artificial General Intelligence, pp. 41-51. Springer, 2011.
Richard S Sutton. Dyna, an integrated architecture for learning, planning, and reacting, ACM Sigart Bulletin, 2(4):160-163, 1991.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-22) 1933.
Martin Troussard, Emmanuel Pignat, Parameswaran Kamalaruban, Sylvain Calinon, and Volkan Cevher. inteacttio-limice inverse reinforcement learning. arXiv preprint utXiv:2007.00425. 2020.
Tingwu Wang, Xuchan Bao, Ignasi Clavera, Jerrick Hoang, Yeming Wen, Eric Langlois, Shunshi Zhang, Guodong Zhang, Pieter Abbeel, and Jimmy Ba. Benchmarking model- reinforcement learning. CoRR, Nww1990700007 2019. URL /att:://arae http:///xxxxvvxx/xaaase wrg/ooggg//.... 1aab//9900 1907 02057
Chenjun Xiao, Yifan Wu, Chen Ma, Dale Schuurmans, and Martin Müller. Learning to combat compounding-error in model-based reinforcement learning. CoRR, abs/1912. 1120,, 2019. URL
14

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1
ALGORITHM
We tested the combination of TBV with two planning algorithms: Monte Carlo Tree Search (equipped with some auxiliary mechanisms) and Best First Search. Here we present the pseudo-code for both algorithms and provide some additional explanation.
A.1.1 BESTFS
In Algorithm we present the pseudocode for BestFSS algorithm used in out experiments. In Data Structures and 5 present two additional data structures used by our implementation of BesFS.
Algorithm 3 BestFS planner
Require:
model
learned model used in Algorithm value function number of nodes expansions per step discount factor
C
Use:
F
priority queue of unexpanded nodes (fringe) graph of all seen nodes
function RESET
F
G
function CHOOSE AATOOSE_ATION(staatto
G.ADD(slale) state & G then state.n_visils
else
state.n_visits state.n_visse pisitss
reachable FIND_ REACHAALLE_NDDES((G EXPAND GRAPH(reachable)
find all nodes reachable from state
best node +- G.FNND BEST NODE(reachable)
b see Algorithm
path + FIND PATH_ (b_st _oodes__odd_____ return
function
for 1 I...C do
n1 -- F.POP SEPOP_BEST_NE DEST_NNDE (0eachhachbble)
D see Algorithm
EXPAND SYPAND_GRAPH.L. (RRAH_NNDD((
function EXPAND EXPAND_GRAPIILNON NODDI,, reachable)
children [
for a E A do SOWLLODDDSSTAEEnsssllee.
new_state &- model.sTEP(a)
new wtwp_state.uncerrttiie
maXaction mod.a.nnerttnniiieeessss..e... http://rtiiitttteeesstttteeaaaaa action)
if new see_sttaee & G then
value
new_ new_state.SET state.SET VALUE()
F.ADD NEW
MADD_NEW___ NEW_NODE(neen _NODE(new (nee_state)
C.ADD_NEW WEW_NNDE(neewwaal
F.REMOVE(n)
> fringe contains only unexpanded nodes
function GET SAT__GRAPHLON OFNNNNNGG
return
15

---

Under review as a conference paper at ICLR 2021
Data structure 4 Fringe (priority queue)
Data structure 5 BestFS graph
Require: SF of nodes
Require: SG set nodes
1: function (OD_N)))(n)
1: function 2DD_NODE(n)
SF.ADD(n)
2:
Sg.ADD(n)
function REMOVE())
3: function
4: SF. Sp.REMOVE(n)
returns max according to keys: (solved, -ivits,, uncertainity)
5: function POP BEST NODE(reachaale))
6: nodes + 11..ITTERSECTTON(rrcchhua
4: function FIND BaaD_BBST__AE BEEEEEENDESTEEEEEE FFFFTT_NDDCcreaacabble,ee state)
7:
return arg naxee n.unncrtaiiitty
5: nodes +- S.NTERSEECTOX((rrcchdll))
6: return LEXICOGRAPPICALL MAXono)
A.1.2 MCTS WITH AVOID HISTORY COEFFICIENT DEAD ENDS AND AVOID SELF LOOPS
In Algorithm we present the general structure of MCTS planner. In Algorithms TO g and
9 we present our version of key functions in MCTS. In Algorithm [1 we provide pseudo code for ad auxiliary dead end mechanism used in this paper. Finally, in Data structure 12 we present the functionality of graph node used in this implementation.
Algorithm 6 MCTS planner
Require:
model
learned model used in Algorithm
V
value funetion ensemble (assigns vector of value estimates to state) number of MCTS passes
C
K
score factor for value uncertainty discount factor dead end value
"dead
Yah
avoid history coefficient
Use:
plamning graph
Spisited
set of states visited by the agent
Saeen
set of states seen in one MCTS pass
function RESET T
function CHOOSS_AATION(SSEE
root + state
for 1...C. do
MCTS_Pa SCCT_PPAS(state)
return arg max www.eaan..cciaee.....a. (n.chid(((((
function MCTS_PASS (CTS_PASS(root)
Saeen
used in Algorithm
11
path, leaf +- TRAVERSAL(root
value t EXPAND LEAF(lea model)
BACKPROPAGATE( (VV ue, path)
function GET GET_GRAPH PTAPPPHHOOAPPPOPPPP return T
16

---

Under review as a conference paper at ICLR 2021
Algorithm 7 traversal()
Algorithm 10 select_child]
Input: root
Input: n
1: <- root
1: if n not expanded or terminal then
2: path +-
return None
3: while n is not a leaf do
if LE__EESD_______ DEAD_END((1) then
4: a - geelct_childdi
return None
5: if is None then & dead end, terminal or leaf
5: else
6:
break
6: Aullowed + ALLOWED(n)
7: path.APPEND((mm)
return
8: n1 4 n.child(a))
arg max aEAaliowed n.child(().BVAA.)
9: return path, n
path
Algorithm Dead end detection
Algorithm 8 expand_
Require: Sseen
Require: "dead V, model
Input: v, path
Input: leaf b MCTS tree node without children
1: function ALLOWED(1)
1: if' leaf is terminal then
Aallowed +- () for a E A
2: UPDATE(leaf.0)
3:
3: return O.
if n.child(aa $ Sseen then
4: else
_S_DEED____ DSS_DEAD_ENDDEAS _EN((lea)) then 5: UPDATE(leaf, Idead)
Aatlowed-ADDD
return Aollowed
6: return "ddead
7:
function IS DEAD END(())
7:
else
8: Aallowed +- -LLLOWE((n)
8:
for E do
if Aallowed then
9:
new-_ooke CREATR_ (OOD(( W .state) new_stoo hou_stateeee model STEP(()) steee t new sew_state if new_state not yet visited then
10:
return False
10:
11:
else
12:
return True
12:
Data structure 12 node
14:
new new_state.valur +
state)
Attributes:
count value
MCTS node counter value ensemble estimate
leaf.child(a) + new_nnode
16: return fvalue
visits
number of agents visits list of children nodes
child
Algorithm 9 backpropagate()
function UPDATE(value)
2:
self.value + sel value + value scounc + scouun +
Require: γ
Input: path
4: function ADD_VISITC,
for (n, a) in reversed(path) do
5: allfvisits. fvisits +
2: + n.reward + T
function EVAL(
3: n.UPDATE(1)
7: $ - SCORE( feeiesselffuuo vealue, self.count)
sld <- STD sellee D uncertainty
of value ensemble
return score score Sel - kstd
A.2 TRAINING SETUP
Code for all our experiments can be accessed at htttta////gthuu..co///mmmmesseee TrustButVerify
Our experiments adhere to the general model-based training loop logic, described in Algorithm ] We use a distributed system with 32 workers solving distinct episodes, where data gathered across batch of workers is collected in common experience buffers: the replay buffer for trainable model of size 50000 and the replay buffer for value function of size 30000. Before the solving of actual episode, collect 1000 random trajectories, that for initial training of the model of
17

---

Under review as a conference paper at ICLR 2021
environment. This initial training has critical importance for the performance of our agents. Episodes are limited to: 600 steps for ToyMMontezuaRReeenee and 1000 steps for the Tower Hanoi.
To update value network for MCTS follow approach Milos et al. (2019) (similar to Hamrick ct al. 2020)) for BestFS experiments we simply calculate future discounted returns for each transition encountered by agent.
A.3 NETWORK ARCHITECTURES FOR MODEL AND VALUE
A.3.1 SINGLE NETWORKS
In every experiments we use two neural network architectures: one to estimate the value function of given state and the other predict the outcome of taking step in the environment. In ToyMR we represent the state as a vector of length 17 and in the Tower of Hanoi as a vector of length 3 x number of dises (it is due one-hot encoding of the peg number for each disc).
In both environments, for value estimation we use an MLP (multilayer perceptron) architecture with two hidden layers of 50 neurons and ReLu non-linearity, For model, in both environments, we use an MLP with four hidden layers of 250 neurons and ReLU activation functions.
The model network has three outputs: the difference between next and current observations (delta target), reward and the episode termination flag (0 or I).
A.3.2 ENSEMBLE
For both value estimation and model we use ensemble of networks with architectures described in Section 1.3.1 The usage of ensembles is however different for value network and model network. Ensemble of model network used as described in Algorithm final result of value is an average of predictions across ensemble. The standard deviation of this predictions multiplied by x is used by MCTS as an auxiliary score added to each vertex the search tree.
case of value estimation, the
In Algorithm 3 we present the procedure of transforming the output of ensemble of model networks to valid prediction of environment signal. In experiments, it turned out to be beneficial to train the model to predict change between observations rather then the ready observations. The transformation performs the following step: collects predictions of all networks in ensemble, then averages next predicted change of observations, predicted rewards and predicted end of episode flags. Averaged observation change added current state, then clipped to the range of possible values (some coordinates of the state vector are binary variables). rounded to integers and returned as the next predicted state. Reward and end of episode flag are predicted to be true if their average value across networks in ensemble is larger than 0.5.
To stabilize performance of value and model ensembles we used additional masks mechanism. We create some number of networks (given by ensemble size parameter), that are trained with the same data buffer, but for prediction each worker uses only random subset of given size (given by number of masks parameter).
A.4 QUANTILE RANK VALUE ANALYSIS
Figure presents performance of BestFS Agent in the Tower of Hanoi environment for different values of Quantile Rank. We observed the the best performance was for values between 0.8 and 0.95, and when the parameter was within the appropriate range of values, the performance was not very sensitive to the changes of quantile rank parameter. We observed similar behaviour in ToyMR experiments the best performance was for quantile rank between 0.9 and 0.95 but was hard to narrow down this interval, due to aforementioned little sensitivity.
18

---

Under review as a conference paper at ICLR 2021
Algorithm 13 Transforming model ensemble predictions
function PREDICT DREDDICTSSTEPstatee
STEP(state, action)
next necrt_observation t-
rewards t- []
is ss_done_fllag t
for network E ensemble do:
(next_obs_deell) reward, is_done) +- -etooookkkPPDDDICiildddd... actioo
action)
next nert_obs + state + next obs delta
next orr._obbberattooos..PPEEEoooeett t_tb)_bbs)__
"euurrss.APPEN((ruuurr)
is_done__laggs.APPENN
predicledd + (VERACrrnerrreewoord)
if predicted reward rewardd 0.5 then
predicted_reunet reward t-
else
predicted_rewarr t- 0 predicted is done + AVERAGE(is_ ficiisddne__fiie done_flags) predicted is done > 0.5 then
predicted_is is is_done <- True
else
predicted_1 -itttedd_sdddeeeeeee False
predicted neat _oarttobss<> t- )
predicled_neste <- gLIVppredicted_neett_ogg
cecdicted_nert____e RoUND(preeictedd_net)
return prennppdeciteddderre nert obs, pressprddicteddeeeeee reward predicted is done)
100
Quantile Rank
0.8
0.85
0.9
0.95
Distance to goal
0.99
0.0
0.5
1.0
1.5
200
25
3.0
Number of steps
1e6
Figure 8: Performance of TBV BestFS on Tower of Hanoi domain with different values of Qantile Rank
A.5 RANDOM TBV REJECTION ANALYSIS
In our preliminary experiments we have seen that without random rejection TBV mechanism the agents often tends get stuck in cycles with high ensemble disagreement and is unable to leave such cycle until the end of episode (since model is not updated in during the episode). Figure 9 we present the performance in Tower of Hanoi for different values of frequency of random TBV
19

---

Under review as a conference paper at ICLR 2021
TBV rejection rate
0.1
0.25
0.5
0.75
Distance to goal
0.9
20
0.5
1.0
1.5
20
25
Number of steps
1e6
Figure 9: Performance of TBV BestFS on the Tower of Hanoi domain with different frequencies of random rejection of TBV
rejection (while the rest of parameters is same as in our best experiments). It can be seen, that if the frequency TBV override (i.e. frequency with which we allow TBV to change planners action) between 0.5 and 0.9 obtained best results. Also, TBV is not very sensitive to this parameter as long it an appropriate range values.
A.6 HYPER-PARAMETERS
In tables] 1 and
2
we present hyper-paramenne used in our experiments.
Toy MR
Tower of Hanoi
Parameter
BestFS
MCTS
BestFS
MCTS
Number of planner passes C'
10
10
10
10
Discounting factor 7 greedy exploration for baslines score factor for value uncertainty x
0.99
0.99
0.99
0.99
0.001
0.02
0.001
0.02
3
Dead end value
-0.2
-0.2
Avoid history coefficient
-0.2
-.2
Value ensemble size 2
20
20
Value ensemble mask size
10
10
10
10
Model ensemble size
8
8
8
8
Model ensemble mask size Optimizer
4
4
4
4
RMSprop
RMSprop 2.5e-4
RMSprop 2.5e-4
RMSprrpp
Learning rate
2.5e-4
2.5e-4
Batch size for value training
32
32
Batch size for model training
1024
1024
1024
1024
See Section A.3.2 for explanation of these parameters.
Table 1: Hyper-paraaeeeen values used in experiments.
For MCTS we took hyperparameters from Milos et al. (2019 As they used setup without learned model needed tune model architecture and model training parameters MontezuuaaR--
20

---

Under review as a conference paper at ICLR 2021
Distance to goal
method
BFS with epsilon-greedy
BFS with TBV
20
RND
PPO
20
Number of steps
1e6
Figure 10: Performance of RND and PPO on Tower of Hanoi with longer training.
venge domain. Then, separately tuned epsilon and Quantile Rank for each combination of domain/planner.
A.7 RND AND PPO
RND continued to further explore state space for Hanoi (figure 10), for comparison we also show performance of PPO (the same parameters RND but without intrinsic reward).
Parameter
ToyMR
Tower of Hanoi
Rollout length
128
128
Maximal length of an episode
600
1000
Total number of rollouts per environment
6200
6200
Number of minibatches
4
Number of optimization epochs
16
Coefficient of extrinsic reward
Coefficient of intrinsic reward
100
10
Number of parallel environments Learning rate Optimization algorithm
32
32
0.001
0.001
Adam
Adam
A
0.95
0.95
Entropy coefficient Proportion of experience used for training predictor
0.001
0.001
1.0
1.0
TE
0.999
0.999
TT
0.99
0.99
Clip range Policy architecture
[0.9, 1.1]
[0.9, 1.1]
FCN
FCN
Table Default hyper-parameters for PPO and RND algorithms for ToyMR and Tower of Hanoi experiments.
21

---

Under review as a conference paper at ICLR 2021
Parameter
Value
Number of optimization epochs Coefficient of intrinsic reward
[1. 4. 16]
[L. 10, 30, 100, 300]
Learning rate
50-0 10 2,5 10
1003 3,5
10 10-1, 3,5-10-4110- 10-4
[0.95,
Proportion of experience used for training predictor YE
[0.25, 1.0]
0.999, 0.9999
[0.99. 0.999
Policy architecture layers number
2, 3, 4
Policy architecture layers width Random target and prediction networks last layer width
644, 128, 256
[64, 128)
Table 3: Hyper-parameters for RND algorithm checked during tuning process of MoyMontezumaRe-
venge.
22


Reviews:
[{"review_id": "ytdyrcImd0L", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a method to guide exploration that prefers to go to areas of the state space for which it is more uncertain. This uncertainty is obtained by measuring the standard deviation of the next state prediction from an ensemble of models. The authors call this the disagreement measure At each step, a search is performed and the disagreement measure is obtained for each state visited. The disagreement measure for each action is compared to the distribution for all the states visited during the search. It it is above some threshold, then the action that maximizes the disagreement measure is taken. Otherwise, it takes the action determined by the search.\n\nThe algorithm presented was unclear. What does planner.choose_action do? Is the heuristic for best-first search (BFS) the disagreement measure? I don't understand how this should help the algorithm pick a good action to take.  The paper says, \"The proposed action is the first edge on the shortest path to the best node in the subgraph searched so far.\" How is the best node determined?\n\nFurthermore, is this search necessary? It seems like it is mainly used as a comparison for the disagreement measure. What if the agent behaved greedily with respect to the disagreement measure all the time. Pathak et al. (2017) used a similar method, but with an inverse model.\n\nI am not quite sure about the comparisons the authors are making. In the case of BFS search, what does it mean to do BFS search with epsilon greedy? Also, this is an artificial curiosity method where curiosity is measured by the disagreement between the ensemble of models. However, there are no comparisons to other curiosity papers, such as Pathak et al. (2017).", "extra_scores": {}, "extra_text": {}}, {"review_id": "nAKAovmTOnF", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a new method which can be combined with graph search algorithms to boost exploration when the uncertainty is high. This new mechanism, called TBV, can override actions given by the model to explore and verify model predictions. It is also shown in the experiments that TBV improves the model performance when combined with MCTS or BestFS. TBV utilizes graph structure of the problem and finds the solution much quicker for both MCTS and BestFS. \n\nWhile the presented method is interesting with high performance, I found many editorial errors in the writing. For example, in the second paragraph of section 3.3, ‘we concentrated of exploration….’, and ‘In our experiments, such a version proved to be effective in in discrete…’, just to name a few. There are so many errors like this and the paper needs serious rewriting. Also, having a conclusion or discussion can help the structure of the paper. \n\nFigure 3 is unclear if the blue line is without TBV with the legend ‘Right corridor visited’. It could be interesting to discuss extension of TBV into continuous environments. Reference format seems to have errors since there are underlines. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "l5v-joks3-l", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an approach for encouraging exploration when planning over learned models of discrete reinforcement learning environment. The proposed method involves using an uncertainty-aware model (e.g., an ensemble of neural networks) to predict state-action transitions, together with a graph-based planner operating on this model. The key idea is to replace (with some probability) the planner's action with the action leading to the highest uncertainty in model prediction. The paper evaluates the proposed technique using two standard search planners (MCTS and BFS). \n\nUnfortunately, I think the significance and technical contribution of this work is minimal, an issue that mostly likely starts from a deficient literature review. What the authors refer to as Trust-But-Verify, it's just an ad-hoc instance of the well-known principle of *optimism in the face of uncertainty*, which underlies classic bandit and RL algorithms such as UCB1[1], UCT[2], Thompson Sampling [3, 4]. In the model-free setting, this idea has lead to numerous recent algorithms, many of which also use ensembles for uncertainty quantification [5-8]. In the model-based setting there are also some precedents of work using similar ideas [9-11]. There is also a large body of work treating the problem from the point of view of Bayesian RL (see [12] for a survey).  It is a bad sign that none of this body of previous work was discussed in the paper, which I would argue was the more relevant literature upon which the paper had to be positioned.\n\nThis could conceivably be excused if the paper technical and experimental contribution was impressive enough, but this is not the case.  In contrast to the literature outlined above (where proposed exploration strategies typically follow from rigorous statistical analysis), this work presents the proposed method as a heuristic rule, providing no insight as to why one should expect the approach to work well in general. Moreover, the experiments are done in relatively simple domain, and compared against simple baselines. Some of the baseline choices do not seem appropriate either. For example, why use $\\epsilon$-greedy for exploration, instead of more robust strategies using upper confidence bounds? \n\nFinally, the writing on the paper can be improved in many places. For example, the paper refers to using the graph structure of the underlying problem, but what this graph structure refers to is not properly defined anywhere in the paper. I imagine it refers to the graph wherein edges represent non-zero probability transitions between states, but this is not clear from the text. Additionally, some paragraphs add little in terms of content. For example, the first paragraph of Section 3 is devoted to describe the basic problem that all model-based RL methods are trying to solve; this issue is ubiquitous so there is no need for a full example and so much text to describe this. Other sentences are unclear, such as \"The optimistic and pessimistic errors are often of the same nature\", which I am not sure what is referring to . Additionally, I didn't see a description of the learned model used in the experiments, which is not an obvious choice, since the environment is discrete. \n\nOverall, to end on a somewhat constructive note, I think the problem the authors are trying to solve is interesting and the proposed approach is based on the right intuitions. However, this work is still too immature for publication. I suggest to the authors to position their work properly with regards to the relevant literature, refine their technical contribution accordingly, and compare with more appropriate baselines.  \n\n----------------------------------------------------------------------\n[1] Auer, Peter, Nicolo Cesa-Bianchi, and Paul Fischer. \"Finite-time analysis of the multiarmed bandit problem.\" Machine learning 47.2-3 (2002): 235-256.\n\n[2] Kocsis, Levente, and Csaba Szepesvári. \"Bandit based monte-carlo planning.\" European conference on machine learning. Springer, Berlin, Heidelberg, 2006.\n\n[3] Thompson, William R. \"On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.\" Biometrika 25.3/4 (1933): 285-294.\n\n[4] Russo, Daniel, et al. \"A tutorial on thompson sampling.\" arXiv preprint arXiv:1707.02038 (2017).\n\n[5] Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., & Munos, R. (2016). Unifying count-based exploration and intrinsic motivation. In Advances in neural information processing systems (pp. 1471-1479).\n\n[6] Ostrovski, G., Bellemare, M. G., Oord, A., & Munos, R. (2017, July). Count-Based Exploration with Neural Density Models. In International Conference on Machine Learning (pp. 2721-2730).\n\n[7] Osband, I., Blundell, C., Pritzel, A., & Van Roy, B. (2016). Deep exploration via bootstrapped DQN. In Advances in neural information processing systems (pp. 4026-4034).\n\n[8] Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., ... & Blundell, C. (2017). Noisy networks for exploration. arXiv preprint arXiv:1706.10295.\n\n[9] Sanner, S., Goetschalckx, R., Driessens, K., & Shani, G. (2009). Bayesian real-time dynamic programming. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-09) (pp. 1784-1789). IJCAI-INT JOINT CONF ARTIF INTELL.\n\n[10] Pathak, Deepak, Dhiraj Gandhi, and Abhinav Gupta. \"Self-supervised exploration via disagreement.\" arXiv preprint arXiv:1906.04161 (2019).\n\n[11] Shyam, Pranav, Wojciech Jaśkowski, and Faustino Gomez. \"Model-based active exploration.\" International Conference on Machine Learning. 2019.\n\n[12] Ghavamzadeh, M., Mannor, S., Pineau, J., & Tamar, A. (2016). Bayesian reinforcement learning: A survey. arXiv preprint arXiv:1609.04436.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AdWpIwRGmV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work tackled the problem of model-based RL in environments where the reward is sparse and many actions are needed to achieve some. Particularly, the authors tried to solve the issue of one-step false loop in the model, which avoids further exploration. Measuring the uncertainty about the built model through ensemble of models, they added a possibility of choosing an action different from what planner suggests, promoting exploration. The work is very-well written in general, especially sections of problem definition and related work. I also appreciate that the proposed method is compared with multiple planners and tested on two different tasks. Having said that, the main missing analysis for me is that the method was not tested on environments where false loop does not exist. Given the nature of the problem definition, i.e. learning the environment, it is counter-intuitive not to test the method on a few standard test-benchmarks without any assumption. The proposed method does not have to get the best result on environments without false loop, but it is important to see how it behaves when the built model is already good. Other than this, I have a few more questions/concerns: \n\n1) The RANDOM parameter seems a little strange, especially because it looks too high, i.e. .5. Some analysis on different values of this (or just with and without RANDOM) on performance would be great. Also, I suspect that change in RANDOM would also change the best QR. I think a plot similar to figure 7, but for RANDOM and combination of RANDOM and QR would improve the paper.\n\n2) The method is about one-step false loop. I would appreciate if the authors talk about multistep false loop briefly. Could it be problematic in learning? If yes, could an extension of this method work?\n\n3) Have the authors considered a QR that changes with number of steps? ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the meta-reviews and the authors comment, the meta-reviewer thinks the paper is not ready for publication in a high-impact conference like ICLR. The paper is not well positioned with respect to the literature, and the proposed techniques are not well discussed in relation with predominant paradigms like optimism in the face of uncertainty.
Decision: Reject