Uncertainty - sensitive learning and planning with ensembles
Authors: Piotr Miłoś
Łukasz Kuciński
Konrad Czechowski
Piotr Kozakowski
Maciej Klimek
Venue:  (2020)
Keywords: deep reinfocement learning
mcts
ensembles
uncertainty

Abstract: We propose a reinforcement learning framework for discrete environments in which an agent optimizes its behavior on two timescales. For the short one, it uses tree search methods to perform tactical decisions. The long strategic level is handled with an ensemble of value functions learned using $TD$-like backups. Combining these two techniques brings synergies. The planning module performs \textit{what-if} analysis allowing to avoid short-term pitfalls and boost backups of the value function. Notably, our method performs well in environments with sparse rewards where standard $TD(1)$ backups fail. On the other hand, the value functions compensate for inherent short-sightedness of planning. Importantly, we use ensembles to measure the epistemic uncertainty of value functions. This serves two purposes: a) it stabilizes planning, b) it guides exploration. 

We evaluate our methods on discrete environments with sparse rewards: the Deep sea chain environment, toy Montezuma's Revenge, and Sokoban. In all the cases, we obtain speed-up of learning and boost to the final performance.

Under review as a conference paper at ICLR 2020
UNCERTAINTT--ENSSIVVV LEARNING AND PLAN- NING WITH ENSEMBLES
A Anonymous authors Paper under double-blind review
ABSTRACT
We propose reinforcement learning framework for discrete environments which an agent makes both strategic and tactical decisions. The former manifests itself through the use of value function, while the latter is powered by a tree search planner. These tools complement each other. The planning module performs local what-if analysis, which allows to avoid tactical pitfalls and boost backups of the value function. The value function, being global in nature, compensates for inherent locality of the planner. In order to further solidify this synergy, we introduce an exploration mechanism with two distinctive components: uncertainty modelling and risk measurement. To model the uncertainty we use value function ensembles, and to rellect risk we use propose several functionals that summarize the implied by the ensemble. We show that our method performs well on hard exploration environments: Deep-sea, toy Montezuma's Revenge, and Sokoban. In all the cases, we obtain speed-up in learning and boost in performance.
1 INTRODUCTION
The model-free and model-based approaches to reinforcement learning (RL) have a comple- mentary set of strengths and weaknesses. While the former offers good asymptotic perfor- mance, it suffers from poor sample complexity. In contrast, the latter usually needs signif- icantly less training samples, but often fails to achieve state-of-the-art results on complex tasks (which is primarily attributed to models' imperfections.. The interplay of model-based and model-free approaches RL has received lot of research attention. This led, for ex- ample, to strong Al systems like Silver et al. 2017 2018) or more recently to Lowrey et al. (2018), which closely related to our work.
When dealing with challenging new RL domains it is helpful to develop tools for address- ing strategic and lactical decision-making. These two perspectives complement each other: strategic perspective is global, static, and often imprecise, while tactical perspective is local, dynamic and exact. We argue that value function can be considered as an example the former, while a planner as example of the latter. Indeed, value function approximators provide noisy estimates (imprecise) of values (static) to every state (global). Conversely, planning provides optimal control, which starting from given state (Iocal) generates actions (dynamic) that are temporally coherent and result in a better-executed trajectories (exact). It is only reasonable value function into the planner, to provide guided heuristics in the local search, shorten the search horizon, and make the search computationally efficient. For complex problems, the above setup has to be supplemented by an exploration stralegy. Such stralegy might be based on modeling uncertainty of the value function approximation (e-g., using dropout sam- pling, variational inference, distributional RL, bootstrap ensemble, etc.). The uncertainty quantified by a risk measure, which is then utilized by a planner to guide exploration.
combine the two into one system. This is achieved by plugging the
Consider a situation of agent with limited memory and computational resources, being dropped into a complex and diverse environment. This setup excludes any hope for brute con-
force strategy and implies that perfect planner is out of reach. In this paper, sider Sokoban, a classic logical puzzle known for its combinatorial complexity and a recent benchmark for RI,, ChainEny, seemingly impossible task also known a 'hay in needle-

---

Under review as a conference paper at ICLR 2020
stack' problem (sce Osband et al. (0118) and Toy Montezuma's Revenge, environment notoriously known for its exploration difficulty (see Guo et al (2019)). Importantly, we focus sparse reward variants of the aforementioned environments (see Section 3]. Since of our method involves planning, an agent has to have an access to the world model. In this paper assume that it is the perfect model. The reason is that challenges presented by the selected environments are the dominating factor driving difficulty of the task (in fact, answering the question of whether Sokoban level is solvable is NP-hard, see e-g. [Do & Zwick (1999)). ) It is also in part due to this fact that a significant body of work dealing with difficult environments makes a similar assumption (sce c.g. Silver et al. 20177 2018
Orseau el. al. (2018b)).
The main contribution of this work showing how recent progress AT can be brought to- gether to improve planning, value function learning, and exploration, in a way that together they form robust algorithms for solving challenging reinforcement learning environments. In particular:
1. For uncertainty modeling, we assume the point of view Osband et al. (2018). which uses ensembles to approximate posterior distribution.
2. In the spirit of Lowrey et al. (0018), we incorporate risk measures to guide explo- ration.
3. For the planner, we base on AlphaZero Monte-Carlo Tree Search (see Silver et al. (2017)), which we enhance with the possibility of exploiting the graph structure of environments and the properties of the optimal solutions.
4. In the value function training protocol, we introduce several improvements, includ- ing a version of self imitation learning mechanism (Oh et al. (2088a)) and hindsight. (Andrychowicz et al. (017)))
The rest of the paper is organized as follows. In the next subsection we provide overview of related work. Tn Section P we present and discuss our method in details. This is followed by a section with experiments and passing to conclusions. We provide code to our work ctw.ob..oommmaaaaaa http:://h/.tttooooooooc/aaaaaaaa
and a dedicated website httpp:///siii httt::///attssgggglllcoo///////t httppp/pal.caoeeaaaaaaaaaaaaaaaa ensembles with more details and movies.
1.1 RELATED WORK
The ideas of mixing model-based and model-free learning were perhaps first stated explicitly in Sutton 1990). Many approaches followed. More recently, in the groundbreaking series of papers Silver et al. (0117), Silver et al. (2018) culminating in AlphaZero, the authors have developed an claborate system that plans and performs modcl-free training to master the game of Go (and others). Similar idcas were also studied in Anthony et al. (2017).
Perhaps, the work which is closest to ours is Lowrey et al. 2018 It argued the paper that an agent with limited computational resources in a complex environment needs both to plan and learn from the incoming stream of experience. Importantly, the value function in Lowrey et al. (2018) is modeled by an ensemble of value functions. The risk measure used to combine them is given by the llg--sun-exp formula' (Lowrey et al. 2018 6). The authors show experimentally that this approach leads to improvements in various continuous tasks, including humanoid training. In our work, we deal with a discrete setting, which enforces different planning module (here MCTS-based). Moreover, we treat more diverse class of risk measures (see Section 2).
Constructing neural network models that would incorporate uncertainty a principled Bayesian way has proven to be challenging and remains and open problem. A promising new results using ensembles include Osband et al. (2018 2017), Lakshminarayanan et al. (2017). Ensembles of models were also successfully used to improve model-based RL train- ing, see Kurutach et al. (2018), Chua et al. 20018) and the references therein. We note that unprincipled ensemble methods
willingly used by RL practitioners. For example, in recent competition Kidzinski et al. (2019) aimed to train an agent able to use a prosthetic leg, four top-ten solutions used some sort of ensembles.
2

---

Under review as a conference paper at ICLR 2020
Another work similar to ours is Guo et al. (2014), in which the authors use MCTS in the role of an 'expert' from which a neural policy is learnt using the dagger algorithm, Ross & Bagnell (2014). The basic difference is that Guo et al. (0014) uses classical MCTS without
value function nor ensembles.
Many works aim to build planning and learning into neural network architectures, e.g. Oh et al. (0177) or Farquhar et al. (017). Kaiser et al. (2019). a recent work on modcl-based Atari, has shown the possibility of sample efficient reinlorcement learning with an explicit visual model. Gu et al. (2016) uses model-based at the beginning phase of training and
model-free methods in 'fine-tuing'. Furthermore. there is a body of work that attempts
to learn the planning module, see Pascanu et al. (2017) Racanière et al. (2017). and Guez al. (2019].
Finally, our paper is related to rescarch focusing study of exploration. Fundamental ro- sults in this area concern the multi-arm bandits problem, see Lattimoree Szepesvári (2018) and the references therein. Methods developed in this area. have been successfully applied in planning algorithmss, see Kocsis al. (2006) and Silver al. (2017 2018). Furthermore, measure with loading variance (delined in Section 2 is related to UCB-V algorithm developed in Auuiibert et al. (2007). Another set of methods have been developed an at-
tempt to solve notoriously hard Montezuma's Revenge, for example Ecoffet et al. (0199)
or Guo et al. (219))
In work
also hindsight, Andrychowicz al. 2017). Its primarily motivation to enrich the learning signal and train generalized value function. However, in certain situation it be considered an exploration algorithm.
2 METHOD DESCRIPTION
In this section, we describe our method: the planning and exploration components, well as the training protocol. Algorithm [ shows how the components are brought together in the training loop. The pseudo-code for planner. run.episode is listed in Algorithm 2 and the remainder pseudo-code can be found in Appendix
Algorithm 1 Learning and planning with ensembles
Require:
Environment env, Model model
1:
Initialize parameters of value function ensemble 0 = (0,,,.,,0k); Vo = (Vo,...., Vox)
2: Initialize replay_buffer buffer
3: repeat
4:
env.reset()
5: episode, solved + planner run episode model, Vo)
b see Algorithm
6:
values evaluate www.uate.epissaeeepppi.....eeeee spisode(eppisodd))
Algorithm
7:
Optionally calculate a mask
> see Appendix
8: bollayybuffer..ddeppiisss
values, solved, mask)
see Algorithm
9: B + replay_bule buffer batch()
B = {55, Ub, mb) see Algorithm
Update Vo by one step of gradient descent
e.g. RMSProp
V
1
Σ (s.u.m)nn
mi (V u0)² C0? for i (1, K}
B
11: until convergence
For the planer component we develop an MCTS-inspired algorithm [ It is novel in two aspects: utilizes risk-sensitive policy (for tree traversal and action choice) intended
MCTS is family of algorithms that iteratively build a search tree, alternating between the following stages: tree traversal, leaf expansion and evaluation, and backpropagation, see Browne al. (2012) for survey the topic.
3

---

Under review as a conference paper at ICLR 2020
to guide exploration, and it includes methods exploiting the graph structure and enables avoiding cycles
The loop avoidance is achieved in two ways: by backpropagation of some fixed negative value through the in-tree path ending with a leaf having no unvisited neightbours (see the pseudo-code in Appendix Alelated to dead ends), and during tree traversal, when the agent encouraged to avoid actions loading to previously visited states on the path (sce pscudo-code related to penalty, in Appendix A). To reinforce this effect, the agent is also encouraged to avoid actions leading to previously visited states on the episode level (see Algorithm where penalty.).
These enhancements combined, make possible learn even in sparse rewards scenarios, which is experimentally demonstrated in Section 3
(all used environments have sparse re- wards). We note that Algorithm 1 is not MCTS specific, other planners could be used as well.
The logic of our MCTS laid out Algorithm 2 We assume that each node of the search tree, say stores visit count count, accumulated value value, accumulated reward n. (a)) and its children are denoted by child(aa) for each action a E A. We define
(o a) = n.wwaar(()) + yn.child(o) value,
where > 0 is discount rate.
Algorithm 2 planner cwmannerrun.eiiiiii rww.episoeeeeeeeee
Algorithm 3 choose actioo()
Require: max max_episode__ie len
Require: avoid_loops
>> Bool
mcts_ jass_pssees
Input: n, seen
penalty. Episode penalty Vo
1: if avoid loops then
b Value function
2: A +- {a E A(n): n.child(a) & seen)
Input:
Starting stale
3:
if A= then > Terminal or dead-end
1: episode +
4:
return None
2: for step
max eex.episede len do
5: else
3: root <-
6:
A A(n((n)
4: root.value root.value cettvvalue-eenatyy..
7: Choose action according to equation
!
5: for 1 to num mcts passes do
a" t- arg max Rene [oa (Q())
6: path, leaf <- traversal(root)
7:
value expand_leaf Vo)
8:
tackproppgatteevvalueepp
8: return a"
9:
+ chooseeacttion(roo,, (root)) (root))
s, r, done model.step(a)
11:
append r))
12: if done then break
13:
return episode, done
Our proposed risk-sensitive exploration method implemented the level of MCTS traver- sal tree, see step 7 in Algorithm 3 Its key defining elements are uncertainty modeling and risk measurement. risk-scnsitive tree traversal policy is defined as follows:
d' a" (n) arg max Eg ( (Q((Qo())). Qo(n) = :' d'
(1)
a
where A is the action space, da I + R is risk mcasure, and Qo is estimator of the Q-function. The postcrior distribution θ models uncortainty in the value estimation.
We implement the posterior θ using ensembles, namely Ea-elf(0) is approximated by 25K f(O)), where K the size of an ensemble. This approximation stems from Osband et al. 2018 Lemma 3), which shows that for Bayesian regression in Gaussian Incar
K
2This is useful for broad class of environments (including the ones we used in the experimental part) for which the optimal trajectory does not have cycles.
4

---

Under review as a conference paper at ICLR 2020
model, generating samples from posterior distribution is equivalent to solving suitable optimization problem, see Appendix [ In our case we use an ensemble of value functions. In some cases, "sub-sample" from 6, which is inspired by Osband et al. (2016) and the classical Thomson sampling (see Appendix C for details).
Using risk measure is inspired by Lowrey et al. (2018), who used (a(x) = ex for x E IR|) and 0. In this paper we consider the following choices of da:
A measure with a loading variance, (1) = va t K > 0. This includes second moments and can be easily generalized to include variance, standard deviation and exploration bonuses.
A relative majority vote (also known plurality vote) measure,
0a(x) = arg max Zo =
(2)
Contrary to the other cases, &a defined in equation dependds not only on marginal
values of its imput, but the whole input (i.e. the estimator vector Qs). It leads a rule resembling optimal Bayes classifier form, iee. the one which chooses minimizing P(aā(s) * a).
The intuitions behind the aforementioned choices of Φa's are as follows. One can think of (a(x) = e*aa used in Lowrey et al. (2018) as measure capluring all moments of value ensemble. For small values of ze 0, it behaves like the measure with loading on variance (via the Tylor expansion). The mean approximates the value of a given action, while the variance quantifies the epistemic uncertainty. Taking weighted sum of these terms (as we do in "mcan+ var" experiments, see Table 3 has the aim of balancing exploitation and exploration. It is also related to UCB-V algorithm, see Audibert et al. (2007). Voting, the other hand, is a well established approach when combining ensembles, see e.g. [Briima (1996) or Rokach (2010). A relative majority vote, in particular, is simple and it can lead to good performance, see e.g. Osband et al. (2016). In the context of planning and RL, it has several interesting properties. In particular, the distribution of votes across ensembles encodes the uncertainty related to the optimal action in a given state. High uncertainty may result in stochastic movement (caused by a uniform tie breaking), and consequently lead to higher exploration. On the other hand, low uncertainty may result in an exploitative behaviour of an agent and, as result, lower exploration. Additionally, voting may improve decision making of an agent in the states, where some action can be dangerons (c.g. lead to irreversible states).
We conclude this section by describing the part of Algorithm related to value functions up- date. The episodes are collected and stored a replay buffer. The replay buffer performs some addition bookkeeping by storing, for each transition, information whether it comes from a solved episode or not (in the case of environments that provide such information, like Sokoban). This mechanism allows sampling batches with a fixed ratio of solved to un- solved transitions (see Algorithm S in Appendix Ap. Such a method resembles self-imitation techniques, e.g. Oh et al. (2018)). The value functions are trained to minimize ly dis- tance from target values sampled from the buffer. The target values can be computed in two modes: bootstrap, which utilizes the values accumulated during the MCTS phase, and factual, corresponding to discounted rewards in an episode (see Algorit g in A Appendix
A). Additionally, some experiments use masks which, analogously to Osband al. (018)), form a mechanism of assigning a transition to a value function (see Appendix C Finally implement ensembles as set of neural networks (we also experiment with multi-headed architectures sharing some lower layers). We use both architectures with or without random priors, for details see Appendix B and Osband et al. (2018)
3 EXPERIMENTS
In this section, we provide experimental evidence to show that using ensembles and risk measures is useful. We chose three environments, Deep-sea, toy Montezuma's Revenge, and
5

---

Under review as a conference paper at ICLR 2020
Sokoban. In all the cases work with single reward versions of the these environments i.c. the agent's is rewarded only upon success completion of its task.
We use MCTS planner with the number of passes equal to 10 (see line 4 of Algorithm 2 We consider this number to rather small for MCTS- like planning methods. Interestingly, observed that such relatively weak planner is sufficient obtain well-preforming algorithm.
We utilize various neural network architectures, Appendix B We measure incertainty using either variance or standard deviation except for the case of Sokoban with randomly-
generated boards, where voting was used, see equation 2
Configuration of the experiments is summarized Table in Appendix
3.1 DEEP-SEA
Deep-sea environment was introduced in (Osband et al. 2018 Section 4) and later included in Osband et al. (2019) as a benchmark for exploration. The agent located in the upper- left corner (position (0, 0)) N N grid, N N. In each timestep, its y-coordinate is
step 0
step 40000
step 120000
step 160000
Figure 1: The heatmaps of standard deviations of ensemble values in the Deep-sea envi- ronment. High values are marked in blue and low in white. At the beginning of training (left picture) the standard deviation is high for all states. Gradually it is decreased in the states that have been explored. Finally (the right) the reward state is found. Note that the upper-right part of the board is unreachable.
increased, while x is controlled. The agent issues actions in [-1,1]. These are translated to slep left or slep right (increasing x by -1 or +1, respectively, as long as x 2 O; herwise remains unchanged) according
prescribed action mask (not be confused with transition masks in Algorithm []. For each step right the agent is punished with 0.01/N. After N steps, the game ends, and the agent receives reward +1 if and only if it reaches position (N, N). The action mask mentioned above is randomized at each field at the beginning of training (and kept fixed).
Such a game is purposely constructed so that naive random exploration schemes fail alrcady for small N's. Indeed, a random agent has chance (1/2)N of reaching the goal even if we disregard misleading rewards for slep right. In Figure [ one can observe how the exploration progresses of our method. In Figure 2 one can see a comparison of non-ensemble models, ensemble models with Thomson sampling (see Appendix C) but without uncertainty bonus (N = 0) and our final ensemble model with uncertainty bonus x = 50. We conclude that both using sub-sampling and ensembles is essential to achieve good exploration (for details see also Appendix
3.2 Toy MONTEZUMA'S REVENCE
Toy Montezuma's 's Revenge is navigation maze-like environment. It was introduced in Rod- crick et al. (2018) to evaluate ideas using higher-level abstractions in long- morizoni prob- lems. While its visual layer is greatly reduced version of the actual Montezuma's Revenge Atari game, retains much the original's exploration problems. This makes it a useful test environment for exploration algorithms, see e.g. Guo al. (2019). In our experiments

---

Under review as a conference paper at ICLR 2020
No ensembles
Ensembles, 00
Ensembles, x 2
3000
25020
namber Gamees
20000
30000
unsetved
unsofved
Talse
False
True
40000
Thue
30
20
M
Figure 2: Comparison of number of episodes needed solve the deep-sea environment with given grid size N. Orange dots marks trials which were unable to solve problem in 30000 episodes. Large problem instances (N 20) are solved only when exploration bonus is used (right-most plot, x = 50)
we work with with the biggest map with 24 rooms, see Figure In order to concentrate on the evaluation of exploration chose to work with sparse rewards. The agent gets reward 1 only reaches the treasure room, otherwise the episode is terminated after 300 steps. It is expected that any simple ex- ploration technique would fail in this case (we provide some base- lines in Table Th. Guo et al. (2019) benchmarks PPO, PPO with self imitation learning (PP)+
PPO with count based exploration bonus +PP++XXP) and their new technique (DTSIL). Only DTSIL is consistently able to solve 24 room challenge, with PPO+EXP occasionally reaching this goal. Our method based on ensembles solves this exploration challenge even in a harder, sparse reward case [ The results are summarized in Table [ We have three setups: no-ensemble; ensemble, no std; ensemble, std. In the first case, we train using Algorithm [ with single neural-network. In the sccond case, for each episode we sub-sample 10 members of ensemble of 20 to be used and the MCTS is guided by their mean. In the final third case, we follow the same protocol but we add to the mean the standard deviation. In our experiments out 43 cases does not leave behind the first room. The setup without explicit exploration std, perform only slightly better. Finally, we observe that ensemble,
13
G
Figure 3: The biggest Montczuma's Revenge map, con- sisting of 24 room. The goal is to reach the room marked with G. The agent needs to avoid traps (marked in red) and pass through doors (marked in blue). Doors are open using keys (marked in yellow).
observe that no-ensembll in 30
bonus, ensemble, std behaves very well.
Further experimental details and the network architecture presented in Appendix and
3.3 SOKOBAN
Sokoban is an environment. known for its combinatorial complexity. The agent's goal is to push all boxes (marked as yellow, crossed squares) to the designed spots (marked
We use a slightly modified code from http:s///gtthhbooooo///rrrgegggs network
SDTSIL builds on the intermediate partial solutions, which are ranked according to their reward, thus suspect it would fail in the sparse reward case.

---

Under review as a conference paper at ICLR 2020
Setup
win-ratio (no. seeds)
visited rooms
no-ensemble ensemble, no std
0 (43)
4.8
2 (40)
5.8
ensemble, std
35 (37)
17.1
Table 1: Result for toy Montezuma's Revenge. We report the number of successful runs and the number of seeds of network initialization. We also show the average number of visited rooms, which is proxy for the learning progress.
square with red dot in the middle), see Figure Apart from the navigational factor, the difficulty of this game is greatly increased by the fact that some actions are irreversible. canonical example such an action is pushing a box into corner, though there multiple less obvious
For-
mally, this difficulty manifests itself the fact that deciding whether level of Sokoban solvable or not, is NP-hard, see e.g. Dor & Zwiick (1999). Due to these challenges the game has been considered as testbed for reinforcement learning and planning methods.
Operationally, generate Sokoban levels we use an automated procedure proposed by Racanière et al. (2017). Some RL ap- proaches solving Sokoban (e.g. Racanière et al. (2017), Guez et al. (2019) assume additional reward signal in the game, e.g. for pushing a box into a designed spot. In this work we sparse setting, that is the agent is rewarded only when all the boxes are put into place.
Figure Example (10, 10) Sokoban board with boxes. Boxes (yellow) are to be pushed by agent (green) to designed spots (red). The optimal solution in this level has 37 steps.
It is interesting to note, that Sokoban offers two explo- ration problems: lingle-level-centricc, where a level-specific ex- ploration is needed, and multi-leval-oenric,, where 'meta- exploration' strategy is required, which works in a level- agnostic manner
quickly adapt. As result, we ducted three lines of experiments using ensembles: a) learn- ing to solve randomly generated bourds(dubbed multiple-
boards Sokoban), b) learning to solve a single board (dubbed as single-boards Sokoban) e) transfer and learnable ensembles.
In our experiment we use Sokoban with board of size (10, 10) and 4 boxes, We use the limit of 200 steps the experiment a) and 100 the remaining ones.
Sokoban, learning to solve randomly generated boards In this experiment we measure the ability of our approach to solve randomly generated Sokoban boards. We measure the performance of the agent by computing the win rate on last 1000 games. In this exper- iment we use ensemble value function using relative majority voting formalized in equation
Multiple-board
5/
00
06-
400
400
No aroeebtss
Figure 5: Learning curve (left axis) and the size of ex- plored graph (right axis) of Sokoban states. The shape of the latter plot may show a gradual switch from ex- ploration to exploitation.
Relative majority voting takes into account the uncertainty of ensem- bles when it comes to the final out- come, not only the uncertainty in assessment of particular action. After 80000 games, our method reaches 85% win rate, com- pared to 76% of agent not using ensembles, Figure 5. As a measure of exploration

---

Under review as a conference paper at ICLR 2020
Architecture
Random
Trans.
Trans.
Trans. 3
5-layers
0.7%
4.9%
7.1%
8.5
4-layers 0.7%
4.3%
5.6%
7.3%
Table 2: Results of transfer experiments. We test transfers from one value function (Trans 1) and transfer from ensembles of 2 and 3 value functions (Trans 2 and Trans 3). In the later two cases the aggregation of values is learned. The results are averaged over 20 seeds.
also present the size of the game graph explored during episodes (red curve in Figure 5 It shows an interesting effect, which can be interpreted as a transition from exploration to exploitation approximately at 40% win-rate mark or, equivalently, 10000 games.
Single-board Sokoban. Learning to solve a single board In this experiment we measure the extent in which our methods can plan and learn single boards. We note that this setting differs substantially from the one the provious paragraph. In the multiple- boards Sokoban there is possibility of generalization from easier to harder scenarios (e.g. randomly initialized network solves 0.7% of boards). Such a transfer is obviously not possible in the single- single-board board case studied here, however there are many attempts on the same board, which enables the agent to explore the board's state space.
For the single-board Sokoban we used experimental settings similar to the one in Section 3.2 see also details in Appendix C We observe that the setup with ensembles solves 73% comparod to 50% the standard training without ensembles. The latter might seem sur- prisingly good, taking into account the sparse reward. This follows by the loop avoidance described in Section 2 If during planning the agent finds itself a situation from which it cannot. find novel state (i.e. encounters dead-end in Algorithm [ negative value, set to 2 in our experiments, is backpropagated in Algorithm 3 to already seen vertices. We speculate that this introduces form of implicit exploration.
In the singe-board board Sokoban case we performed also experiments on (8, 8) boards with 4 boxes obtaining success rate of 94% compared to 64% on the standard non-ensemble settings.
Transfer and learnable ensembles Generating any new board can be seen as a cost. dimension along with sample complexity. This quile naturally happens in meta-learning problems. We tested how value functions learned on small number of boards perform on new previously unseen ones. We used the following protocol, trained value function fixed number of 10 games. To ease the training we used relabeling akin to Andrychowicz et al. [ We evaluate these models other boards. It turns out that they typically quitc weak, arguably it is not very surprising as solving 10 boards does not give much chance to infer 'the general' solutions. In the second phase we use ensembles of the models. More precisely, we calculate the values of n = 2.3 models and aggregate it using a small neural networks with one fully connected hidden layer. This network learnable and trained using the standard setup. We observe that the quality of such ensemble increases with the number of components as summarized in Table g We observed high variability of the results over seeds, this is to be expected as board in Sokoban significantly vary in difficulty. We also observe that maximal results for transfer increase with the number of value function, being approximately 10%, 11% and 12%. This further supports the claim that ensembling may lead to improved performance. In 5-layer experiment we use a network with 5 hidden cun layers, details in Appendix B compare this with an analogous 4 layers network. In the latter case, we obtain weaker result. We speculate this might be due to the fact that smaller architecture easier to overfit.
5 More precisely, for failing trajectory choose a random time-step and shift the target spots that they match the current location of boxes. We note that although this operation requires the knowledge of the game mechanics (i.e. its perfect model) it is used only in this phase

---

Under review as a conference paper at ICLR 2020
CONCLUSIONS AND FURTHER WORK
In this paper, we introduced a reinforcement learning method that blends planning, learning, and risk-sensitive approach to exploration. We verified experimentally that such setup is useful in solving hard exploration problems, iee. problems characterized by sparse rewards and long episodes (c.g. spanning even hundrods of stops).
We believe that this opens promising future research directions. There are multiple ensemble design choices, and we tested only a selected few. Additionally, there are more ways for combining the results of ensembles and it would be interesting to see if one, relatively general, method can be found. Such a result. would be a step towards deep Bayesian learning.
In our work, we used MCTS with a perfect model of deterministic environments. It would be interesting to consider problems requiring the use of learned, imperfect models. This is more demanding lask, and it is intriguing whether the approach lo uncertainly developed here could be useful dealing with model imperfections. Equally important research direc- tion would be related to solving stochastic environments. This might be considerably more difficult as such a task requires disentangling epistemic (studied in this work) and aleatoric (coming from the environment) uncertainties.
We focused our attention on the Monte-Carlo Tree Search, but there is a priori no reason why some other planning should not yield better results. In some initial experiments obtained promising, but yet inconclusive, result using the Levin tree search (see Orseau el. al. (2018a))- Another templing direction is training both value function and policy, akin to methods of Silver et al. (0177)
It would also be interesting isolate the proposed exploration method from the planner and see how it fares when coupled with model-free algorithms. This fits along the lines of some recent research directions, see e.g. Agarwal al. (2019).
Going further, we speculate that it may be possible to use the methods developed for Sokoban in the meta-learning and continual learning grounds problems. Perhaps measures of uncertainty can be used to enable a learning system to adapt to a changing environment. In an archetypical case, this might be obtained by choosing from ensemble model (a skill) which is useful at the moment and understanding situations that such a model is not yet present.
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. Striving for simplicity in off-policy deep reinforcement learning. arXiv preprint arXic:1907.04553 2019.
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Picter Abbecl, and Wojeiech Zaremba. Hind- sight experience replay. In Advances in Newral Information Processing Systems 30: An- nual Conference Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 5048 5058, 2017. URL http::/paperr. .nip.. cctpseer//
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In NIPS, 2017.
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Tuning bandit algorithms in stochastic environments. In International conference on algorithmicc leurning theory, pp- 150-165. Springer, 2007.
Leo Breiman. Bagging predictors. Machine learning, 24(2):123-140) 1996.
Cameron B Browne, Edward Powley, Danicl Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computa- tional Intelligence and AT in games, 4(1):1-43, 2012.
10

---

Under review as a conference paper at ICLR 2020
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforce- ment learning in a handful of trials using probabilistic dynamics models. In NeurIPS 2018, pp. 4759-4770, 2018.
Dorit Dor and Uri Zwick. Sokoban and other motion planning problems. Computational Geometry, 13(4):215 228, 1999.
Adrien Fcoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Go- explore: new approach for hard-exploration problems. CoRR, abs/1901.1099) 2019. URL http:///rxii. otggab///901. 10995
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treequ and atreec: Differentiable tree planning for deep reinforcement learning. CoRR, abs/1710.11411 2017.
Shixiang Gu, Timothy Lillicrap, Πya Sutskever, and Sergey Levine. Contimuous deep q-learning with model-based acceleration. In ICML, 2016.
Arthur Guez, Mehdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Theophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, Greg Wayne, David Silver, and Timothy P. Lillicrap. An investigation of model-free planning, In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 2464-2473, 2019. URL http://prroceddins.. press/v97 gquzz9a.htmn
Xiaoxiao Guo, Satinder P. Singh, Honglak Lee, Richard L. Lewis, and Xiaoshi Wang. Deep learning for real-time atari game play using offline monte-carlo tree scarch planning. In NIPS, 2014.
Yijie Guo, Jongwook Choi, Marcin Moczulski, Samy Bengio, Mohammad Norouzi, and Honglak Lee. Efficient exploration with self- learning via trajectory-conddiioned policy. CoRR, abs/ 1901.10077.177 2019. URL aett:///rxivv wwwrxiiv.oor/aaae
www.oos/////eeeeeoooeoo.ooeo.eee htt///bb//9990 /9907 10247
Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H. Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, Ryan Sepassi, George Tucker, and Henryk Michalewski. Model-based reinforcement learn- ing for atari. CoRR, abs/ 1903.00374, 2019. URL http://arxiv wttpd///.rrrab//990333 htt////b0119000003/// 00374 htthhtp:://a//ttt
Lukasz Kidzinski, Carmichael F. Ong, Sharada Prasanna Mohanty, Jemnifer L. Hicks, Sean F. Carroll, Bo Zhou, Hong-cheng Zeng, Pan Wang, Rongzhong Lian, Hao Tian, Wojciech Jaskowski, Garrett Andersen, Odd Rune Lykkebö, Nihat Engin Toklu, Pranav Shyam, Rupesh Kumar Srivastava, Sergey Kolesnikov, Oleksii Hrinchuk, Anton Pechenko, Mattias Ljungström, Zhen Wang, Xu Hu, Zehong Hu, Minghui Qiu, Jun Huang, Aleksei Shpilman, Ivan Sosin, Oleg Svidchenko, Aleksandra Malysheva, Daniel Kudenko, Lance Rane, Aditya Bhatt, Zhengfei Wang, Penghui Qi, Zeyang Yu, Peng Peng. Quan Yuan, Wenxin Li, Yunsheng Tian, Ruihan Yang, Pingchuan Ma, Shauharda Khadka, Somdeb Majundar, Zach Dwiel, Yinyin Liu, Evren Tumer, Jeremy D. Watson, Marcel Salathé, Sergey Levine, and Scott L. Delp. Artificial intelligence for prosthetics - challenge solu- 2019. URL http: http///xxvv.o.o org/ abs. hetp:/992..000 094411212221111111
tions. CoRR,
Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1, 2006.
Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model- ensemble trust-region policy optimization. CoRR, abs/1182.11099) 2018.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NIPS 2017, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, 2018.
Kendall Lowrey, Aravind Rajeswaran, Sham Kakade, Emanuel Todorov, and Igor Mordatch. Plan online, learn offlin: Efficient learning and exploration via model-based control. CoRR, abs/1811 1.0888, 2018.
11

---

Under review as a conference paper at ICLR 2020
Junhyuk Oh, Satinder Singh, and Honglak Lec. Value prediction network. In NIPS, 2017.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. arXiv preprint or orxiv:1806. 100.166060555, 2018a.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Tee. Self-imitation learning. In Proceedings of the 35th International Conference on Machine Learning, 1CML 2018, Stockholmssässsan Stockholm, Sweden, July 10-15, 2018, pp. 3875 3884, 2018b. URL http:://rocce http:://proceedigss mlr. www.s//00//ooaaeeet oh18b. html
Laurent Orseau, Levi Lelis, Tor Lattimore, and Theophane Weber. Single-agent policy tree search with guarantees. In Advonces in Neural Information Processing Systems 31: Annual Conference on Newral Information Processing Systems 2018, NewrIPS 2018, 9-8 December 2018, Montréal, Canada., pp. 3205--221,, 2018a. URL sett://paperss nips. thattttttgaeeesssse
Laurent Orscau, Levi Lelis, Tor Lattimore, and Théophane Weber. Singlo-agent policy tree scarch with guarantces. In Advances in Neural Information Processing Systems, pp. 3205 3215, 2018b.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In NIPS, 2016.
Tan Osband, Daniel Russo, Zheng Wen, and Benjamin Van Roy. Deep exploration via randomized value functions. CoRR, abs abs/1173.07608, 2017.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. In NewrIPS, 2018.
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepezvári, Satinder Singh, Benjamin Van Roy, Richard S. Sutton, David Silver, and Hado van Hasselt. Behaviour suite for reinforcement learning. CoRR, abs/1 abs/1908.085 1908.03568, 2019. URL httt:://arrd..orr//b///00000 .03668
Razvan Pascanu, Yujia Li, Oriol Vinyals, Nicolas Heess, Lars Buesing, Sébastien Racanière, David P. Reichert, Theophane Weber, Daan Wierstra, and Peter Battaglia. Learning model-based planning from scratch. CoRR, abs/1707.06170, 2017.
Sébastien Racanière, Theophane Weber, David P. Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adrià Puigdomenech Badía, Oriol Vinyals, Nicolas Heess, Yujia Li, Razvan Pascanu, Peter Battaglia, Demis Hassabis, David Silver, and Daan Wierstra. Imagination-auggeente agents for deep reinforcement learning. In NIPS, 2017.
Melrose Roderick, Christopher Grimm, and Stefanie Tellex. Deep abstract newtoss... In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pp. 131-138, 2018. URL
http://dl. acm. org/ citatiio. cfm71d=32374099
Lior Rokach. Ensemble- based classifiers. Artificial Intelligence Review, 33(1-2):11 39, 2010.
Stéphane Ross and J. Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. CoRR, abs/ hhs/1406.5979, 2014. URL http://arxiv. www.oogg///....o..oooooo.ooo..b. 1406. 5979
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicra,, 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 Schrittwieser, Ioannis Antonoglon, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learn- ing algorithm that masters chess, shogi, and Go through self-play. Science, 1144:1140- 1144, 2018.
12

---

Under review as a conference paper at ICLR 2020
Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In ML, pp. 216 216-224. Morgan Kaufmann, 1990.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25. No. 3/4, 1933.
13

---

Under review as a conference paper at ICLR 2020
A ALGORITHM
In this section we detail the building blocks of Algorithm 1 As mentioned in Section the key elements of MCTS (sce Algorithm are tree traversal, leaf expansion, and backpropagate, shown in Algorithm Algorithm 6 and Algorithm respectively. Algorithm
7 shows the update of a tree node. In particular, Algorithm 1 shows how the value function enters the picture, by evaluating all of the leaf's children (line 9). Algorithm A Algorithm both use variable penalty, This is a penalty corresponding to entering the same states during tree traversal (hence is operates on the planner level) and the change applied during traversal, and undone during backpropagation.
Algorithm 4 traversal()
Igorihhm 6 expand leaf ()
Require: penalty,
Planner penalty
Require: dead_eed_value, V
Input: root
Input: leaf
1: n + root
1: if leaf is terminal then
2: path +
2: update(leaf,0) 0.)
3: while n is not a leaf do
3: return 0.
4: n.value n.value-
else if leaf is a dead-end then
5: a- thoose_action(n, path)
5: update(leaf, dead end value) return dead end value
6: if a is None then
b Dead-end
7: break
7: clsc
8: (ath.append((..a)
for a E A(leaf)
9: n 4- child(((a)
v v (e(affcchild/0 9:
10: return path, n
b path
10:
leaf.chile (aailddd).valuee
11: return 1eaf. value
Algorithm backpropagatee)
Require: penalty, 7
Algorithm 7 update
Input: v, path
Input: n, value
1: for (n.a) in (pat)sed(path) do
1: n.value + n.value + value
2: n.value t n.vuue -.value-penalty, penalty,
2: n.count +- n.count
3: v v + yv
4: update(n.v)
The following blocks of code are related to the training setup. Algorithm g is responsi- ble for computing an appropriated value for each element of the episode. There are two available modes: "bootstrap", which utilizes the values accunulated during the MCTS phase, and "factual", which represents the sum of discounted rewards in the episode. In the "bootstrap" mode we undo the penalty applied during the episode generation stage (line in the Algorithm 2 The inner details of replay buffer, in particular Hindsight and self-imitation, is given in Algorithm g and Algorithm 10] Hindsight refers to any method that processes episode, and potentially overrides states values (see lines 1-2 in Algorithm 9h. Algorithm [0 shows the way batch is generated. First, for each transition it is deter- mined whether it should be sampled from a solved or unsolved episode (according to a fixed ratio). Second, game is sampled from population determined in the previous step, with probability proportional to the game length. Finally, given a game a transition is chosen uniformly.
14

---

Under review as a conference paper at ICLR 2020
Algorithm 8 evaluateeepisode( ()
Algorithm 9 replay-buffer add()
Require:
D String penalty. Episode penalty
mode
Require:
D
> Replay Buffer
H b Hindsight mapping
Input:
episode solved ?
> {(St, de, rt) > Bool Discount rate
Input: episode {(0,, Ct, Tt. wx) value solved
b {vr
> Bool
1: + len(epsiode)
mask
Binary vector Hindsight
2: values + (0.....)) RT
1: for t = to T do
3: if mode="bootstrap" then
2: 1/ H(pissode),
4: rewards <- va.. + penalty.)
3: D + DU (((5t, ar, u.) solved, mask)
5: else if mode="factual" then
6: rewards + 0,
Algorithm 10 heplay-buffal batch
to do 8: values:-1 + Yvalues; + rewards;
7: for =
Require: D
Replay Buffer Batch size
size
9: return values
ratio
unsolved
1: Initialize B+0 0
2: for b= 1 to size do
3: if b ratio%1 then
4: select + False
5: clse
6:
select <- True
7:
D' - (d D: d.solved select)
8:
Sample d D with
prob(d) x len(d.episode)
9:
Sample (s, v. m) uniformly from
10: B +- B U [(s, m,m)
11: return
B ARCHITECTURES
Deep-sea For Deep-see environment we encode state as one hot vector of size N2, and learn simple linear transformation for value estimation.
Toy Montezuma Revenge Observation represented as tuple containing current room location, agent position within the room and status of all keys and doors the board. To estimate value we use fully-connected neural networks with two hidden layers consisting 50 neurons each.
Single-board Sokoban Observation has shape (10, 10, 7) where first two coordinates are spatial and the third coordinate one-hot encodes type of state (e.g. box, target, agent, wall). To estimate value we flatten the observation and apply fully-connected neural networks with two hidden layers consisting neurons each.
Multiple-boards Sokoban Here the same observation type as in the single-board problem. Each value function network composed of five 3 x 3 convolutional layers with with stride 1, followed by two fully connected layers with 128 units and 1 unit, respectively.
C TRAINING DETAILS
Randomized priors In Osband et al. 20188 Lemma 3) showed that for Bayesian linear regression setting with Gaussian prior and noise model, generating samples from posterior distribution equivalent to solving appropriate optimization problem. To be exact,
15

---

Under review as a conference paper at ICLR 2020
suppose D {2 34) is the dataset, fo(x) x²0 is the regression function, c, is a Gaussian noise, i comes from Gaussian prior, and y/s + Ez. Then the solution of the following problem
arg min 11ū. (fo (o) c110112
for some < > O, is a sample from the posterior ODD. Consequently, Osband et al. (2018) propose to use equation [ as a training objective and include randomized prior in the va ue function approximator. This objective matched with the one used in Algorithm and some of our experiments include randomized priors.
Masks An important decision for training, is how assign transitions the particular elements of value functions ensemble. This is implemented using masks, see Algorithm is considered in an update step (see lines 9-10 of Algorithm [ a let (s, v, m) E B be a transition. mask m {0, i) has the following interpretation: mh if and only if the transition t is used to train Ve,, i= 11
1 Suppose a batch
We experimented with the following versions of masking:
dynamic masks: masks are generated anew whenever transition sampled from replay buffer,
static masks: cach transition assigned a fixed mask generated when addod to the replay buffer.
In the cases of dynamic masks, each batch was split equally among the elements of ensemble (for this we kept the batch size to be the multiplicity the number of ensembles). The static masks were inspired by the Bootstrapped DQN, see (Osband et al. 2016 Appendix B), where it is a core idea. We experimented with applying a different mask to each transition according to the Bernoulli distribution, the same trajectory.
assign the same masks for all transitions in
We found it useful to use static masks in the Deep-sea, Toy Montezuma's Revenge and Single- board Sokoban experiments, and dynamic masks Multiple-board Sokoban experiments.
Ensembles sampling Recall that equation involves calculating the expected value, Ea-e, with respect to the posterior distribution O In some experiments we instead sub- sample from O Such an approach follows Osband al. (2016), which in turns is inspired by the classical Thomson sampling (see discussion (Osband et al. 2016, Section 4) and the original Thompson (133)). To be concrete, for given a risk measure &a equation Iaattiionnreuur reduces to
Σ Da (Q. (n)) (n = (n. d' d'E AA)
a" (n) arg max
(4)
BEC
where & (1, (1...., K). Sub-sampling, with fixed parameter e, is equivalent to computing equation! with taken as a random subset of {I,...,K) K} of cardinality L.
Hiperparameters Table 3 below, summarizes the parameters of the training used in the Deep-see, Toy Montezuma's Revenge, Single-board Sokoban and boordss Sokoban experiments presented in Section
16

---

Under review as a conference paper at ICLR 2020
Parameter
Deep-sea
Toy MR
Single-b. Sok.
Multiple-b. Sok.
Number of MCTS passes'
10
10
10
10
Ensemble size K²
20
20
20
3
Ensemble sub-sampling e
10
10
10
Risk measure4
mcan +ttdd mcan std
mcan- seeant-ste std
voting
50
9
n a
VF Larget
boolstrap
bootstrrap 0.99
bootstrap
factual
Discounting 7
0.99
0.99
0.99
Randomized prior
no
no
n1
yes
Optimizer"
R.MSProp
RMSProp 4
RMSProp
RMSProp
Learning rate
2.5e
2.5e
2.5e
4
2.5e 4
Batch size"!
32
32
32
32
Mask 12
static
static
static
dynamic
num mcts passes the MCTS algorithm, see Algorithm
2 the number of value functions ensemble in Algorithm
3 the parameter of ensemble sub-sampling
meon+fstd stands for mean + std, where mean is the mean of the ensemble predictions and its standard deviation. voling stands for using as given by equation
see footnote 4
6 see description in Section 2 and Algorithm
7 used in Algorithm Section and Appendix
9 optimizer used step 10 Algorithm
optimizer's ' learning rate
11 cardinality of batch B in line 9 of Algorithm line 10 of Algorithm
Table 3: Default values of hyperparameters used in our experiments.
17


Reviews:
[{"review_id": "HkgcGAHAFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 paper proposes an approach blending model-based, model-free methods and utilizing risk-sensitivity information in ensembles as part of the value estimation and exploration process. The exploration is based on risk- sensitivity measures such as moments and relative majority vote. There is a lot of work currently trying to marry the model free with model based approaches for integrated planning and learning as the authors have mentioned in the related work section of the paper and also called out similar methods and techniques. The authors have provided evidence via experiments in three environments and shown good results of using this blended approach. Code is also provided for others to further carry out explorations in this research area.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlP92j69H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "Uncertainty-Sensitive Learning and Planning with Ensembles\n=====================================================\n\nThis paper investigates the use of uncertainty-aware estimates in solving planning problems (RL with access to simulator).\nThe proposed algorithm combines a learned model-free value estimate with MCTS planning.\nAn ensemble of neural networks is used to model posterior uncertainty in the value estimate and drive efficient exploration.\n\n\nThere are several things to like about this paper:\n- The paper takes on several core issues in RL/planning research, most notably the synthesis of dealing with model-based and model-free uncertainty in RL.\n- The general flavour of the paper + algorithm seems to be reasonable. The proposal to use ensemble uncertainty estimates to drive model-based MCTS is interesting, natural, and I think it's a good one.\n- The proposed structure of the paper is quite nice, there is mostly a linear and logical progression of complexity in the experiments. This is nice to see clear benefits of the approach on the simplest possible settings and build up from there.\n- The effort to open source code + implementation details is laudable.\n\nHowever, there are several places where this paper falls short:\n- In general, the claims and results of the paper are far too vague to be fully understood and replicated. Take the main algorithm 1, it really seems like more of a \"sketch\" of a very general family of algorithms, rather than a specific description of a clear algorithm.\n- This vagueness is spread throughout the plots and figures as well... note that Figure 1 has no indication of how many steps have been evaluated, and Figure 2 has no indication for what value K > 0 was actually used. The clarity does not improve in Sections 3.2 and 3.3 where quite inconsistent performance metrics and presentations are presented.\n- Generally, the writing could be tightened quite a lot. In particular I would encourage you to think about whether each statement you make is clearly supported by some theorem, experiment or plot in your paper. For example, on page 3 \"We found this mechanism to be beneficial... see Section 3.3\" but then it's not clear exactly what statement shows that particular part of the mechanism was helpful, versus other issues associated with ensemble learning. There are more than a few typos... the on(e) in Osband... akin to ??... might be obtained by choosing from (the) ensemble...\n- It would be very helpful to clarify that the agent is given access to a simulator... so that this is not exactly the typical RL setting of sequential decision making. This should appear early in the paper.\n- The code that is released with the paper is also quite confusing, it is not structured with a clear README and includes many sections of dead/commented code. I was hoping the code might rescue some of the clarity, but I think that still needs work.\n\nOverall, I do think there is some interesting material here...\nIt's an important problem, and the core building blocks of combining model, value and uncertainty for better exploration is interesting.\nHowever, I just think the actual paper is not clear enough on the details.\nMy belief is that going through this paper very methodically and carefully to make sure that every single detail + claim is rigorously supported would help this paper immensely.\nFor that reason I have to say that I think it's a \"reject\" in its current form.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1lRg1qtcS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 propose to combine planning methods like MCTS with an ensemble of value functions to a) estimate the value of leaf nodes of the search tree and b) use the ensemble estimate of uncertainty to guide exploration during MCTS search. \nThe MCTS rollouts are also used as optimization targets for the value function.\n\nI believe this is a clear reject. On the one hand, the paper needs signficiantly more work on the writing and clarity. On the other hand I have several worries on the method and evaluation side. \n\nRegarding the presentation of the paper:\nOverall, the paper seems quite rushed. This is not a strong reason for rejection but should be improved in a future version. For example, punctuation and sentence structure is often wrong, the paper has only slighlty over 7 pages, a citation is undefined on p.7 and images and whitespace is formatted wrongly on occasion (e.g. top of page 6).\nMore importantly, on the content side, the experimental section is sufficiently clear and well written, however, the method description needs more detail and background information. The paper relies on several prior works which are referred to but not described (E.g. MCTS , the sampling mechanism by Osband et al. which they are using but not describing, the 'mask' from Osband et al which they are using but not describing).\nFurthermore, the algorithm itself is not described in sufficient detail:\n- How does the 'soft-penalization' work?\n- How exactly does the mechanism \"similar in fashing to\" Thomson sampling work?\n- Are you learning a model or do you have access to the true transition function?\n\nRegarding the method:\nI can't say anything definitive about the method as I'm not entirely clear how exactly it works. However, I have several worries that might need addressing:\n- It seems to me that the method relies on access to the _true_ transition and reward function and not on a learned model. This is a big difference to much of the prior work they compare against. This also makes the comparison against any pure model free method like PPO much less meaningful.\n- Similarly, manually avoiding dead-ends and loops is a very strong assumption \n- Also, being able to distinguish and use a fixed ratio of \"solved\" and \"unsolved\" episodes is a strong assumption. \n- The one main contribution seems to be a new way of how \\phi_a(x) is defined. Their particular choice needs a clearer motivation. Furthermore, if there is more contribution and differences to prior work, highlighting them more would help the reader understand the contribution. \n- As the work makes several strong assumptions regarding the environment and access to the model, significantly more work (e.g. ablation studies) is needed to clearly show which assumption and feature of the algorithm is important for performance (and ideally also why). For example (but that's just a first idea): To understand the impact of their choice of \\phi vs. their planning architecture, it would be be interesting to maybe train PPO using an exploration bonus based on \\phi. This would allow disentangling the contribution of: Access to the true model, \"discrete-environment-tricks\" like penalizing dead-ends, and exploration incentivication of \\phi. \n\nEdit:\nThank you for your response and the updated manuscript, which reads considerably better.\nI also agree with your point regarding the strength of assumption regarding \"solved\" and \"unsolved\" episodes.\n\nConsequently, I will raise my score to a \"weak reject\" to express that I think this is promising work.\n\nI do believe that ablation studies would add a lot to the paper as they would allow one to see which of the (many) added components help how much, for example between the selection function $\\phi$ and the various penalizations used. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study planning problems with sparse rewards.                                                                           
They propose a tree search algorithm together with an ensemble of value                                                            
functions to guide exploration in this setting.                                                                                    
The value predictions from the ensemble are combined in a risk sensitive way,                                                      
therefore biasing the search towards states with high uncertainty in value                                                         
prediction.                                                                                                                        
The approach is applied to several grid-world environments.                                                                        
                                                                                                                                   
The reviewers mostly criticized the presentation of the material, in particular                                                    
that the paper provided insufficient details on the proposed                                                                       
method. Furthermore, the comparison to model-free RL methods was deemed somewhat                                                   
lacking, as the proposed algorithm has access to the ground truth model.                                                           
The authors improved the manuscript in the rebuttal.                                                                               
                                                                                                                                   
Based on the reviews and my own reading I think that the paper in it's current                                                     
form is below acceptance threshold. However, with further improved presentation                                                    
and baselines for the experiments, this has potential to be an important contribution.
Decision: Reject