Structure and randomness in planning and reinforcement learning
Authors: Piotr Kozakowski
Piotr Januszewski
Konrad Czechowski
Łukasz Kuciński
Piotr Miłoś
Venue:  (2021)
Keywords: reinforcement learning
uncertainty
model-based
MCTS

Abstract: Planning in large state spaces inevitably needs to balance depth and breadth of the search. It has a crucial impact on planners performance and most manage this interplay implicitly. We present a novel method $\textit{Shoot Tree Search (STS)}$, which makes it possible to control this trade-off more explicitly. Our algorithm can be understood as an interpolation between two celebrated search mechanisms: MCTS and random shooting. It also lets the user control the bias-variance trade-off, akin to $TD(n)$, but in the tree search context.

In experiments on challenging domains, we show that STS can get the best of both worlds consistently achieving higher scores. 

Under review as a conference paper at ICLR 2021
STRUCTURE AND RANDOMNESS IN PLANNING AND REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Planning in large state spaces inevitably needs to balance depth and breadth the search. It has crucial impact planners performance and most manage this interplay implicitly. We present a novel method Shoot Tree Search (STS), which makes it possible to control this trade-off more explicitly. Our algorithm be understood as an interpolation between two celebrated search mechanisms: MCTS and random shooting. It also lets the user control the bias-variance trade-off, akin to T (n), but in the tree search context.
In experiments on challenging domains, we show that STS can get the best of both worlds consistently achieving higher scores.
INTRODUCTION
Classically, reinforcement learning is split into model-free and model-based methods. Each of these approaches has its strengths and weaknesses: the former often achieves state-of-the-art performance, while the latter holds the promise of better sample efficiency and adaptability to new situations. Interestingly, in both paradigms, there exists non-trivial interplay between structure and randomness. In the model-free approach, Temporal Difference (TD) prediction leverages the structure of function approximators, while Monte Carlo (MC) prediction relies on random rollouts.
Model-based methods often employ planning, which counterfactually evaluates future scenarios. The design of planner can lean either towards randomness, with random rollouts used for state evaluation (e.g. random shooting), or towards structure, where data-structure, typically tree or graph, forms a backbone of the search, e.g. Monte Carlo Tree Search (MCTS). Planning is a powerful concept and an important policy improvement mechanism. However, in many interesting problems, the search state space is prohibitively large and cannot exhaustively explored. Consequently, is critical to balance the depth and breadth of the search in order to stay within feasible computational budget. This dilemma is ubiquitous, though often not explicit.
The aim of our work is twofold. First, present novel method: Shoot Tree Search (STS). The development of the algorithm was motivated by the aforementioned observations concerning structure, randomness, and dilemma between breadth and depth of the search. It lets the user control the depth and breadth of the search more explicitly and can be viewed as bias-variance control method. STS itself can be understood as an interpolation between MCTS and random shooting. We show experimentally that, on a diverse set of environments, STS can get the best of both worlds. We also provide some toy environments, to get an insight into why STS can be expected to perform well. The critical element of STS, multi-step expansion, can be easily implemented on top of many algorithms from the MCTS family, As such, can be viewed as one of the extensions in the MCTS toolbox.
The second aim of the paper is to analyze various improvements to planning algorithms and test them experimentally. This, we believe, of interest its own right. The testing was performed on the Sokoban and Google Research Football environments. Sokoban is challenging combinatorial puzzle proposed to be a testbed for planning methods by Racanière et al. (2017). Google Research Football is an advanced, physics-bas based simulator of football, introduced recently in Kurach al.) (2019). It has been designed to offer a diverse set of challenges for testing reinforcement learning algorithms.
The rest of the paper is organized as follows. the next section, we discuss the background and related works. Further, we present details of our method. Section devoted to experimental results.

---

Under review as a conference paper at ICLR 2021
2 BACKGROUND AND RELATED WORK
The introduction to reinforcement learning can be found in Suttton & Barto 2018 In contemporary research, the line between model-free and model-based methods is often blurred. An early example is Guo et al. (2014), where MCTS plays the role of an 'expert' in DAgger (Ross & Bagnell (014)).
policy learning algorithm. In the series of papers Silver et al. 2017 2018), culminating in AlphaZero. the authors developed a system combining elements of model-based and model-free methods that master the game of Go (and others). Similar ideas were also studied in Anthony et al. (2017). In Milos et al. (2019), planning and model-free learning were brought together to solve combinatorial environments. Schrittwieser (2019) successfully integrated model learning with planning in the latent space. recent paper, HHmmrick et al. (020)) suggests further integration model-free and model-based methods via utilizing internal planner information to calculate more accurate estimates of the Q-function. Soemers et al. (2016) presents expansion much similar to ours. The crucial algorithmic difference is the aggregate backprop (for details see Section 3). In similar vain, [Coulom proposes a framework blending tree search and Monte-Car Carlo simulations in a smooth way. Soemerrs et al. (2016) and Coulom (2006) differ from our work as they do not used learned value functions, resorting to heuristics and/or long rollouts. In Dames et al. (2017) a detailed empirical analysis suggests that the key to the UCT effectiveness is the correct ordering of actions. As most of these works, we use the model-based reinforcement learning paradigm, in which the agent has access to true model of the environment.
Searching and planning algorithms are deeply rooted in classical computer science and classical AI, see e.g. Cormen al. (2009) Russell & Norvig (2002). Traditional heuristic algorithms such as A* (Hart et al. (1968) ) or GBFS (Doran & Michie (1966) are widely used. The Monte Carlo Tree Search algorithm, which combines heuristic search with learning, led breakthroughs in the field,
see |Browne et al. (2012) for an extensive survey. Similarly, Orseau et al. (2018) bases on the classical BFS to build heuristic search mechanism with theoretical guarantees. In Agosttnilll et al. (2019) the authors utilise the value-function to improve upon the A algorithm and solve Rubik's s cube.
Monte Carlo rollouts are known to be a useful way of approximating the value of a state-action pair Abramson (990)). Approaches in which the actions of rollout are uniformly sampled are often called flat Monte Carlo. Impressively, Flat Monte Carlo achieved the world champion level in Bridge Ginsberg (2001) and Scrabble Shhepaard 2002).
Moreover, Monte Carlo rollouts are often used as a part of model predictive control, see Camacho & Albal (2013). As suggested by Chua et al. (2018); Nagabandi et al. (2018), they offer several advantages, including simplicity, ease of parallelization. At the same time, they reach competitive results to other (more complicated) methods on many important tasks. Williams et al. (2016) applied their Model Predictive Path Integral control algorithm (Williams et al. 2015), the approach based on stochastic sampling of trajectories, the problem of controlling a fifth-scale Auto-Rally vehicle in an aggressive driving task.
Some works aim to compose a planning module into neural network architectures, see e.g., Oh et al. (2017); Farquhar et al. (2017). Kaiser et al. (2019), recent work on moodel-based Atari, has shown the possibility of sample efficient reinforcement learning with an explicit visual model. Gu al.) (201)) uses model-based methods at the initial phase of training and model-free methods during 'fine-tuning'. Furthermore, there body of work that attempts to learn planning module, see Pascanu et al. (2017); Racanière et al. (2017); Guez et al. (2019).
METHODS
Reinforcement learning (RI. is formalized with the Markov decision processes (MDP) formalism see Sutton & Barto (2018). An MDP is defined as (S,A, A P, P,r, 7), where S is a state space, A is set of actions available to an agent, /' is the transition kernel, r is reward function and E (0, is the discount factor. An agent policy, object central to the MDP formalism is the value function V= S + R associated with policy π (s) := E, Σ 7're|50 = s) where r, denotes the stream of rewards, assuming that the agent operates with policy (which is denoted as FTy) and that f the system starts from The
S + P(A), maps states to distribution over actions. An
2

---

Under review as a conference paper at ICLR 2021
objective is to find policy, which achieves maximal value. In this work concentrate planning methods, which in each step search a subspace of the state-space to render robust decision.
A Generic Planner, presented in Algorithm ! gives unified view all methods analyzed in the paper: Random Shooting, MCTS and, our novel approach, STS. By a suitable choice of functions SELECT, EXPAND, UPDATE and CHOOSE CHOOSE_ACTION, description below).
recover each of these methods (see
Typically, planner is part of reinforcement learning (RL) training process, Algorithm 2 In positive feedback loop, the planner improves the quality of data used for training of the value function Vo and policy к Conversely, the policy and value function might further improve planning. Implementation details of Algorithm are provided in Appendix A.1
Algorithm 1 Generic Planner, defines required constants, variables and objects used in further algorithms
Algorithm Training loop, additionally requires environment env
# Initialize parameters of Va, T
Require:
C
planning passes planning horizon discount factor
# Initialize replay_buffe fer
repeat
episode + COLLECT EPISODE COLLECT_EPISODE replay_but Suroouubuuferr.DDeppiooo
Use:
N(s, a)
visit count total action-value
W (s,
B B replay_bbu fuuf fer.BATCH BATCH
(s,a)
mean action-valus
Update Va. using B and SGD until convergence
Vo
value function policy
function DILLEECTEPPSDDE
To model
environment simulator
$ 5 ENVRESSET
episode +
Initialize N, W,W.C Q to zero function PLANNER(state)
repeat
<- PLANNER(S)
for L...C'do
8' r env.STEP(a)
path, leaf SELECT(state)
spisode.APPEND((s......
rollout, leaf + EXPAND(leaf) UPDATE(path, rollout, leaf)
until episode is done return CALCULATE TARGET(episode)
return CHOOSR_ACTION(staas,
Below give a detailed description of the planning methods considered in the papers.
Random Shooting In this section we present two instantiations of Algorithm D which use Monte Carlo rollouts evaluate state-actions pairs: Random Shooting and Bandit Shooting, see Algorithm 3 and Algorithm respectively.
Algorithm 3 Random Shooting Planner
function SELECT(state)
function UPDATE(path, rollout, leaf)
f- state
G
- -"
==1 + + Vo(leaf)
~ (T(ss.))
where rx rollout
s'.r +- mTdeL_
8, + apr
return (s, s'
quality r
function EXPAND(leaf)
W(s,a) W(s, a) quality
80 leaf
N(s,a) < N(s,a) +1
rollout (Sk, ak, TH+1)
Q(8,a) + Wis.a)
Nis.a
where #k41, &- model and ag ~ (8()))))
function CHOOSE ACTION(s)
return rollout,
return arg max, Q a)

---

Under review as a conference paper at ICLR 2021
Algorithm 4 Bandit Shooting Planner, additionally requires exploration weight Cpuct
function SELECT(state)
function EXPAND(leaf)
$ - state a(s t E ((s.a')(11 ((), arg max (Q(8, (ss a))((s)))
Same as in Algorithm function UPDaTElpath, rollout) Same as in Algorithm function [HOOSE_ACTIONS: return arg max, (s,
s'r model.sTEP(s..0
return (8,0,)) s
The simplest version of Algorithm 3 the so-called flat Monte Carlo Ginsberg (2001) Sheppard (2002), does not use a policy a (instead rollouts are uniformly sampled) nor value function Vo (just
truncated sum of rewards with the pre-trained PPO policy in Section 4.2 Bandit Shooting, presented in Algorithm 4 is
>x k= rk)). The value function is neither used in the experiments
Multi-armed Bandits variant of Random Shooting and uses PUCT Silver et al. (2018) rule to improve exploration and thus achieve more reliable evaluations of actions.
Algorithm 5 MCTS, additionally tree structure tree, requires exploration weight Cpuct and action sampling temperature 7
function SELECT(state)
function UPDATE(path, rollout, leaf)
state
quality +- Vo(leaf)
path +
for 8, a, reversed(path) do
while belongs to tree do a <- SELECT CHILD(s)
quality + -+ quality
(x,,a) <- W(s,a) quality
s' r- tree(s (s,..APPEND((ssarr)) 3 s'
((s,a) <- N(s.
Q(s,a) W(s.a)
N(s.a)
return path, s
function SELECT CHILD(s)
(8 v Ve, N(s, a')/(1 + N(s, a))
function EXPAND(leaf)
a - arg max, [(s (o
for do
return
tree[]eaf][[] + (5',
function CHOOSE ACTION(s) a ~ softmax log ((s,))) return
W(1eaf, a) t- r Va(s')
N(leaf, a)
Q(leaf, + W (1eaf,a))
return leaf
Algorithm Shoot Tree Search
function EXPAND(Leaf)
function UPDATE(path, rollout, leaf)
leaf rollout +- for 1... H do
s' leaf
C C+ 1
quality <
MCTS (CTSSEXXPND(s)
for a. + reversed(path rollout) do
a f- CHOOSE [ICTON]AACTIO((S) ACTION(s)
i path then
8', r + tree [s][]] rollout. ((IIout. 5-s
7-0 0
else
ve Vo(s')
return rollout, s
c ct
function SELECT(state)
quality + csr x (quality +v)
Same as in Algorithm function PHOOSE_ACTIONS
5
(s, + W(s, quality
((s + N(8,a) +
((s,a) W(s.)
Same as in Algorithm
N(s.0)
5' +
MCTS Monte Carlo Tree Search (MCTS) is family of methods, that iteratively and explicitly build a search tree, see Browne et al. (2012). It follows the schema of Algorithm SELECT traverses down the tree, according in-tree policy, until leaf is encountered. EXPAND grows the tree by
4

---

Under review as a conference paper at ICLR 2021
adding the leaf's children. The values of these nodes estimated, usually with the help of rollout policy in a similar vein as Random Shooting Planner, or via the value network Vo (see Silver et al. (017)). In this work, refer to the latter version, using value networks, as MCTS. Finally, UPDATE backpropagates these values from the leaf up the tree. After planning, CHOOSF_ACTT chooses action to take by sampling from the empirical child visitation distribution, sharpened by predefined temperature parameter This is consistent with MuZero, as used in the Atari domain (Schrittwieser, 2019). A basic variant of MCTS is presented in Algorithm More details are
provided in Appendix A.5
Shoot Tree Search Shoot Tree Search (STS) extends MCTS novel way, by redesigning the expansion phase, see Algorithm [ Given a leaf and planning horizon H the method expands И consecutive vertices starting from the leaf. Each new node is chosen according to the in in-tree policy and is added to the search tree. Note a erucial difference between STS and vanilla MCTS using random rollouts: in contrast to the latter, STS adds visited nodes to the tree, so the explored paths can easily be branched out during later planning passes. We call this mechanism multi-step expansion. Intuitively, multi-step expansion tilts slightly the search towards DFS. Its advantage comes from making "faster advances" towards the solution, though possibly at risk of missing some promising nodes. Our experiments support these intuitions, suggesting sweet-spot around H = 10 (see experiments in Table 4.1 and Section A.9.II)
A similar method was proposed in Soemers et al. (016), with two crucial differences. First, Soemers al. (2016) uses hard-coded heuristics while we embed STS into the RL training. Second, in Soemers et al. (2016) only the last estimate of value is backpropagated. Our UPDATE backpropagates an aggregate value estimates calculated on the rollout of multi-step expunsion. We weight this update by the rollout length (hence N(s.a) u) <- N(s, a) + c). We consider our method more natural and, importantly, it presents better experimental results; see also Section
STS can be viewed interpretation, STS interpolates between the two methods. We demonstrate empirically that the change introduced by STS is essential to solving challenging RL domains; see Section 4 We note that H = corresponds to MCTS.
sophisticated version of Random Shooting applied to MCTS. In this
Interestingly, in some of experiments, identified that the tree traversal performed during SELECT was the computational bottleneck. The cost of building the search tree is quadratic with respect to its depth. STS allows to significantly reduce this cost since a single tree traversal adds not one but H new nodes. To get this computational benefit we tweak UPDATE to backpropagate all values from 1 and ro lout in one pass. A more formal analysis of computational gains is presented in Lemma I
Equipping STS with additional exploration mechanism (see Appendix A.5 A.4
and A.6 can
guarantee that every state action pair will be visited infinitely often. Combining this with Robbins- Monro conditions for learning rate, implies the convergence in tabular case, following the classical tabular Q-learning convergence theorem (see Tsitsiklis 1994)).
4 EXPERIMENTS
We tested the spectrum of algorithms presented in Section 3 on the Sokoban and Google Research Football domains. Those tasks present numerous challenges, which evaluate various properties of planning algorithms. Our experiments support the hypothesis that STS build a more efficient search tree. This is strengthen by measuring the tree size isolation (see Table its average depth (see Section A.9.I) and comparisons to AlphaGo (see Section A.9.2) For the training details, list of bhper-parameters parameters and network architectures are presented in Appendix A.1 Appendix A.2 and Appendix A.3 respectively.
We stress that in all comparisons, we set parameters C, H so that MCTS and STS perform the same number of node expansions during each PLANNER call; Algorithm [ This ensures the same computational power requirements (e.g., number of neural network evaluations) and similar memory
usage.
In Appendix A.10 we present two thought experiments, supported by formal proofs, where we argue that STS can better handle certain errors in value functions by using the multi-step expansion. We
5

---

Under review as a conference paper at ICLR 2021
show that STS can get quicker to the regions with the accurate values during planning and it is less prone to entering decoy' paths. The errors are inevitable during training and when using function approximators.
Scenario
H
rate
Np
Nt
Ng
4.1 SOKOBAN
256
1
95.2%
1224
1224
716
Sokoban is well-known combina- torial puzzle, where the agent's goal is to push all boxes (marked as yel- low, crossed squares) to the designed spots (marked squares with red dot the middle), see Figure I Addi- tionally, to the navigational challenge, Sokoban's is difficulty is attributed to the irreversibility of certain actions. A typical example is pushing box into corner though there are multi- ple less apparent cases. The environ- ment's complexity formalized by the fact that, deciding whether level of Sokoban is solvable or not, is PSPACE-complete, e.g. Dor Zwick (1999). Due to these challenges, the game often used to test reinforcement learning and planning methods.
av. loops
64
4
96.5%
299
1194
830
16
16
95.7%
114
1822
1333
4
64
89%
62
3960
1491
256
1
84.5%
1497
1497
376
no av. loops
32
8
88.4%
185
1483
409
128
65.3%
36
4589
967
Table I: Comparison evaluation of MCTS and STS. C, H are parameters in Algorithm [ S. rate the ratio solved boards, Np. Ne(== N, H), Ng are the average number passes, tree nodes and game states observed until the solution is found. Full table is available in Table
We use procedurally generated Sokoban levels, as proposed by Racanière et al. (2017). The agent is rewarded with by putting a box into a designated spot and additonally with 10 when all the boxes are in place. We use Sokoban with the board of size (10, 10).4 boxes, and the limit of 200 steps. We use an MCTS implementation with transposition tables and loop avoidance mechanism, see Miloš et al. (019)) and Appendix A.5
In the first experiment, we evaluated the planning capabilities of STS in isolation from training. To this end, we used pre-trained value function (we used MCTS to get this) and varied the number of passes C' and the depth of multi-step expansion H, such that H C remains constant. In this way, we ensure a fair comparison because the same computing power is used. In Table 1 we present quantities (Np, Ne, Ng),, which measure planning costs. Arguably, the most important of these is Nr. which denotes the total size of the planning tree used to find the solution. In the two presented scenarios, there is sweet spot for the choice of H. For this choice, the number of tree nodes, Nr, is the smallest, and even more importantly, we observe an increase in the solved rate. This may possibly be explained by the fact that the number of distinct visited game states, No, grows. This suggests that STS explores more aggressively and efficiently.
Figure 1: Example (10, 10) Sokoban board with 4 boxes. Boxes (yellow) by agent (green) to designed spots (red). The optimal solution this level has 37 steps.
be pushed
In the second line of experiments, we analyzed the training performance (see Algorithm 2 For MCTS we used C 50 passes per step, while for STS considered C 10 passes with multi-step expansion H = 5. The learning curve for STS dominates the learning curve for MCTS, which persists throughout training, see Figure 2 Since the difficulty of Sokoban levels increases progressively, the achieved improvement is substantial, even though in absolute terms, it may seem small.
To better understand where the differences in performance stem from, we evaluated MCTS with 50 passes and STS with 10 passes and 5 steps of multi-step expansion, both without the avoid loops mechanism. We found that 68% of boards is solved by both MCTS and STS, 10% only by STS, and 2.1% only by MCTS. On several examples, we observed that STS could recover better than MCTS from errors in value function, which are relatively localized in the state space, even though they might be quite significant in value. This can be attributed to multi-step expansion, which exits from the erroneous region more quickly by correcting biased value functions estimates with deep search (note that deep paths, while introducing more variance, will stronger discount biased value function).

---

Under review as a conference paper at ICLR 2021
The downside is that sometimes STS is overoptimistic, pushing into dead-end states. We include the detailed analysis on the example room in the Appendix AA7.3
Methods based on random shooting perform poorly for Sokoban: evaluated Bandit Shooting (Algorithm 4) which struggled to exceed 5% solved rate. Only when the difficulty of boards was significantly reduced, to the board size of (6, 6) with 2 boxes, this method achieved results above 90%. Our shooting setup included applying loop avoidance improvements. This feature is highly effective in the case of MCTS (and STS) but did not bring much improvement for shooting methods. Details are provided in Appendix A.7.2
We conclude with conjecture that for domains with combinatorial complexity, tree methods (MCTS or STS) significantly outperform shooting methods, and STS offers some benefits over MCTS.
STS is predominantly meant improve search for small computational budgets. In Appendix A.
we present also result for a ten times bigger budget of H C' = 500.
1:07
6:7
Pleess
D75
8.7 251
1.5
17
Figure 2: Learning curve for Sokoban domain. Left figure shows full results, right one inspects the same data for limited interval values on the y axis. The results are averaged over 10 runs, shaded areas shows 95% confidence intervals. The axis is the number of collected samples.
4.2 GOOGLE RESEARCH FOOTBALL
Google Research Football (GRF) is an environment recently introduced in Kurach et al. (2019). It is an advanced, physics-based simulator of the game of football. It is designed to offer set of challenges for testing RL algorithms. At the same time, is highly-optimized and open-sourced. GRF is modeled after popular football (a.k.a. soccer) video games, fun and engaging for humans. As such, it requires both tactical and strategical decision- decision-making. This makes it an interesting benchmark for planning algorithms. A part of GRF is the Football Academy consisting of 11 scenarios highlighting various tactical difficulties, see Kurach et al. (2019 Table 10) for description. Due to its diversity, the GRF Academy an excellent testing ground of planning methods listed in Section 3 including STS. GRF provides several state representations, including internal game representation as well as visual observation. We tested both of them: the former was processed with an MLP architecture, while the latter with a convolutional neural network. Details are provided in Appendix A.I
One feature which makes GRF hard (and thus interesting) for planning its relatively large action space (19 actions). From the perspective of the design of a low budget planner, this can be viewed as a challenge.
A GRF Academy episode is considered finished after 100 steps or when the goal is scored by the agent. The game is stochastic, hence we report the solved rates over at least 20 episodes per environment. In Table[2 we compare STS with various other methods. To the best of our knowledge, no prior work has evaluated model-based methods on Google Research Football. Hence we provide two baselines: model-free PPO results, reported by the authors of GRF, and model-based AlphaZero implemented by us with a minor enviromment-spectin we use Q-network Q(s, a) instead of value network V(s) to evaluate all actions at the same time when expanding a leaf. We provide an ablation on this architectural choice in Appendix A.9.
modification. To efficiently deal with the large action space,
We report the median of the solved rates in at least three runs with different seeds.
Random shooting For each of the Random Shooting and Bandit Shooting planners (Algorithm 3 and Algorithm 4 respectively), we performed two batches of experiments: with and without training.
7

---

Under review as a conference paper at ICLR 2021
The former used two different state representation and, consequence, two different architectures (MLP and Conv.). The latter used a uniform policy (flat) or pre-trained policy (PPO). For all the variants, set C' 30 passes and planning horizon H 10. More details can be found in Appendix[A.]
The flat version cannot solve GRF Academy tasks. This is rather unsur- prising and confirms that it is chal- lenging test suite. The Bandit Shoot- ing algorithm generally offers a better performance both when using the pre- trained policy or training from scratch. This indicates that handit-based ex- ploration results in more reliable esti- mates of action values. Bandit Shoot- ing Conv. experiments are better than the baseline in 6 cases and worse in This shows that, at least in some environments, planning can improve performance. We also tested whether mixing the policy with Dirichlet noise (see /ilver et al. 2018)) and sampling an action to take in an environment can impact exploration and training performance. Nevertheless, the results were inconclusive (see Appendix [A.4 for details). can be seen that the corner scenario is particularly challenging: the baseline scores on the lower end of the spectrum, the shooting algorithms rather underperformed and the training was quite unstable. The results improved significantly under the STS algorithm. In the Shooting experiments, we used approx. 1.5M training samples (median).
Figure 3: Example from the Google Football League
STS and MCTS STS achieves state-of-the-art results on the GRF Academy and significantly outperforms other methods. For STS we used C' 30 passes with H = 10 and for MCTS we set corresponding C 300.
STS Conv. completely solves 8 out of academy environments and is the best or close to the best on the remaining 3. One can observe that in Corner, Counterattack easy and hard, Pass and shoot with keeper, Run to score with keeper, and Single goal vs. lazy academies the difference between STS and MCTS, as well as most of the other methods, is substantial. See Table for exact results. We stress that STS Conv. easily beats any other method in one-to-one comparison across all academies. STS MLP achieves close second place. These results provide further evidence that STS gives boost in environments requiring long-horizon planning. This stands in sharp contrast with MCTS, which was not able achieve impressive results in the considered time budget. We found that exploration was a challenge in GRF Academy environments. Namely, training often got stuck in disadvantageous regions of the state space, which was caused by unfavorable random initialization of the value function. To deal with it, the last layer of the value function neural network was initialized to We suspect this zero-initialization method might be useful other domains as well, Our findings is consistent with recent recommendations of (Andrychowicz et al.) 20200 Section 3.2) given in the model-free setting. In the STS experiments we used approx. 0.8M training samples (median).
More details can be found in Appendix A.8 including ablations. They indicate that multi-step expansion of STS blends well with various elements of the MCTS toolbox as well as demonstrate the impact of the aforementioned sero-initialization.
CONCLUSIONS AND FURTHER WORK
In this paper, we introduced a new algorithm, Shoot Tree Search. STS aims to explicitly address the dilemma between depth and breadth search in large state spaces. That touches upon interesting issues of using randomness and structure search algorithms. The core improvement multi-step expansion, which may be used control the depth of search and inject into planning via random multi-step expansions. Having empirically verified the efficiency this extension in many challenging scenarios, argue that it could be included in standard MCTS toolbox. We
randomness
8

---

Under review as a conference paper at ICLR 2021
3 vs. with
Counterattack
Counterattach hard
Empty goal
Empty goal close
Pass and shoot
with keeper
Run pass and
shoot with
Run to score
Run to score with keeper
Single goal
versus lazy
keeper
Comer
keeper
Method
easy
PPO
0.90
0.10
0.70
0.65
0.90
1.00
0.65
0.90
0.90
1.00
0.90
Random
Shooting
flat
0.10
0.00
0.05
0.10
0.00
0.95
0.05
0.10
0.00
0.00
0.00
PPO
0.45
0.10
0.10
0.30
1.00
1.00
0.25
0.80
0.80
0.20
0.30
MLP
0.90
0.87
0.80
0.73
0.93
1.00
0.87
0.70
0.90
0.37
0.67
Bandit Shooting
flat
0.20
0.10
0.00
0.00
0.05
0.35
0.05
0.05
0.05
0.00
0.00
PPO
1.00
0.05
0.95
0.80
1.00
1.00
0.55
1.00
0.85
0.45
0.60
MLP
0.87
0.47
0.73
0.60
1.00
1.00
0.90
0.80
0.93
1.00
0.60
Conv.
0.97
0.41
0.81
0.44
0.97
1.00
0.94
0.69
1.00
0.91
0.00
MCTS Conv.
0.81
0.50
0.31
0.31
0.99
1.00
0.45
0.89
0.70
0.00
0.00
STS
MLP
1.00
0.78
1.00
0.97
1.00
1.00
0.94
0.97
1.00
0.94
0.94
Conv.
1.00
0.81
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.97
0.97
Table Summary of selected algorithms' performance on GRF, Entries are rounded solved rates.
PPO results come from Kurach et al. (2019)
speculate that the effectiveness of STS stems from better balance between breadth and depth search. While our experiments support this claim, we plan a more detailed analysis, possibly using methods developed in James al. (2017).
There are many interesting follow-up research directions involving STS. One of them concerns the automatic choice of the multi-step expansion depth, H, during training. This could not only improve the performance of the method, but also alleviate the necessity for fine-tuning this additional hyper-parameter. Another, quite natural extension of this work is use learned models. As research question, this typically splits into two sub-problems: learn an accurate model, or adjust the planner to accommodate for the model's deficiencies. An exciting research avenue, is related to a multi-agent version of GRF This constitutes an open challenge both for planning and learning models.
is interesting to study STS itself. Historically, the fusion of different multi-step estimates (such as TD(A) or GAE) lead to significant improvements, and it is only natural to ask if a similar advancement can be reached here. Moreover, STS could be combined with different statistical tree search methods, where statistics other than the expected value (e.g. max) are stored and updated (see e.g. AAgostinelli al. (2019)). The method could also augmented with uncertainty estimation (e.g. in the spirit of Milos et al. (2019) strengthen the exploration, and consequently the algorithm.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bruce Abramson. Expected-Outcone General Model of Static Evaluation. JEEE Transactions on Pattern Analysis and Machine Intelligence, 1990. ISSN 01628828. doi: 10.1109/34.4444..
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.10088/442266001-00000000 URL bottps://doi.orree 1038/
647256-019-00740
Marcin Andrychowicz, Anton Raichuk, Piotr Stanczyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pictquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters in on-policy reinforcement learning? A large-scale empirical study. CoRR, org/ abs/2006 05990
abs/2006.05990, 2020. URL http:::
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In NIPS, 2017.
Cameron B Browne, Edward Powley, Daniel 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 Computational Intelligence and Al in games, (1):1-43, 2012.
Eduardo F Camacho and Carlos Bordons Alba. Model predictive control. Springer Science & Business Media, 2013.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems, pp. 7754-4765. 2018.
Thomas H Cormen, Charles Leiserson, Ronald I. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In H. Jaap van den Herik, Paolo Ciancarini, and H. H. L. M. Donkers (eds.), Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers, volume 4630 of Lecture URL
Notes in Computer Science, pp. 72-83. Springer, 2006. doi: 10.
https://doii http///o...ggg/..// 1007 9978 3- -55--5538---81
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https
//github. com www.///peaaaaaaaeeience..o
2017.
Dorit Dor and Uni Zwick. Sokoban and other motion planning problems. Computational Geometry, 13(4):215-2) 2288, 1999.
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 1966.
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.
Matthew L. Ginsberg, GIB: Imperfect information in computationally challenging game. Journal of Artificial Intelligence Research, 2001. ISSN 10769757. doi: 10.1613/jair.800.
Shixiang Gu, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. Continuous deep qelearning 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 Timo- thy P. Lillicrap. An investigation of model-free planning. In Proceedings the 36th International Conference on Machine Learning, JCML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 2464-2473, 2019. http:htt:://proeeeee ngs m www.srrss/eeee... guez 9a html
10

---

Under review as a conference paper at ICLR 2021
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 search planning. In NIPS, 2014.
Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Tobias Pfaff, Theophane Weber, Lars Buesing, and Peter W. Battaglia. Combining q-learning and search with amortized value estimates. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. URL SkDRaTrKDS
net www./neeet/ttiioiio
Peter E Hart, Nils Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-101; 110000007,-0 1968.
Steven James, George Dimitri Konidaris, and Benjamin Rosman. An analysis of monte carlo tree search. In Satinder P. Singh and Shaul Markovitch (eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pp. 3576-3582. AAAI Press, 2017. URL
org/ /twg///c///////////////////// www.iindxxx.p.. bwa.dex.ppp/aae whwpppp........
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 reinforcemmet learning for atari. CoRR, abs/1903.00374, 2019. U.L//cppp///rxx..oorr//bb///
00374
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, and Sylvain Gelly. Google research football: A novel reinforcement learning environment, arXiv preprint 1907. 11100, 2019.
Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, and Sylvain Gelly. Google research football. httt:s///ggttab..ccooooool---ee
2019.
Piotr Mitos, Lukasz Kuciński, Konrad Czechowski, Piotr Kozakowski, and Maciek Klimek. Uncertainty-sensitive learning and planning with ensembles. arXiv preprint arXiv: 1X1i::912.00999 2019.
Anusha Nagabandi, Gregory Kahn, Ronald S. Fearing, and Sergey Levine. Neural network dy- namies for model-based deep reinforcement learning with model-free fine-tuning. In 2018 IEEE International Conference Robotics and Automation, ICRA 2018, Brisbane, Australia, URL
May 21-25, 2018 pp. 7559-7566. IEEE, 2018. doi: 10.1 2019///AA.2018.84420
https: / aog.oorg/00000 1100..11900 1101111911H0 CAR09////RA... TWW.IICAAAAA......
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In NIPS, 2017.
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 on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada,, pp. 3205-3215, 2018
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/1 abs/1707.06170, 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.
Stéphane Ross and J. Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. CoRR, abs/1406.5979, 2014. URL
wtt.////....//////1111... 5979
Stuart Russell and Peter Norvig. Artificial intelligence: modern approach. 2002.

---

Under review as a conference paper at ICLR 2021
Antonoglou Ioannis Hubert Thomas Simonyan Karen Sifre Laurent Schmitt Simon Guez Arthur Lockhart Edward Hassabis Demis Graepel Thore Lillicrap Timothy Silver David Schrittwieser, Julian. Mastering Atari, Go, Chess and Shogi by Planning with Learned Model. arXiv preprint arXiv: 1.00265, 2019. htt.tttss:///attttt /tt.htttp.s//xxx..ooo///aaa/ss
08265
Brian Sheppard. Wottd-chammiionsiip-caliiir Scrabble. Artificial Intelligence, 2002. ISSN 00043702.
doi:
David Silver, Julian Schrittieserr, 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 Schrittwieser, 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:1 140-1 144, 2018.
Dennis J. N. Soemers, Chiara F. Sironi, Torsten Schuster, and Mark for real-time monte-carlo tree search in general video game playing. In IEEE Conference on Computational Intelligence and Games, CIG 2016, Santorini, Greece, September 20-23, 2016, pp. 1-8. IEEE, 2016. doi: 10.1109/CIG.201..7 77664488. http:tss: /doi: www.oi..ogg///0 /llg////000 1109/ CIG. 2016. 7860448
Winands. Enhancements
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
John N Tsitsiklis. Asynchronous stochastic approximation and q-learning, Machine learning, 16(3): 185-202, 1994.
G. Williams, Drews, Goldfain, M. Rehg, and E. A. Theodorou. Aggressive driving with model predictive path integral control. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 1433-1440. IEEE, 2016. doi: 10.1109/CRA.2211.74877711
Grady Williams, Andrew Aldrich, and Evangelos Theodorou. Model Predictive Path Integral Control using Covariance Variable Importance Sampling. sep 2015. URL /ttt:://aatt wwt.vvbr.//ss.././///
1509. 01149
12

---

Under review as a conference paper at ICLR 2021
A.1
TRAINING DETAILS
We provide the code of our methods and hyper-parameters configuration files in com/ com/shoot: tree searchearaaee sts
The training loop follows the logic of Algorithm 2 We use a distributed setup with 30 workers and a replay buffer of size 30000. We perform 1000 optimizer updates batches of transitions whenever all workers collect and store one full episode. During batch sampling, we ensured an equal amount of examples from solved and unsolved episodes. In GRF and Sokoban experiments, each episode was limited to 100 and 200 time steps, respectively.
value function approximator, Ve, is trained via the MSE loss using targets calculated by COOUULATT_TARGEAA In shooting experiments we use "reward-to-go" targets Σi=44 1 - where T is the terminal time-step in episode. In MCTS and STS in GRF experiments (see Section A.3 for details) we use "tree action-values" targets, similar to the one used Hamrick et al. (2020) Miloš et al. (2019).
Policy, To, is trained using the cross-entropy loss. As targets, we use one-hot encoded actions chosen in the environment for Random Shooting and the empirical distribution of actions chosen in the root during the planning for Bandit Shooting, MCTS, and STS.
The total loss is weighted (weighted by 1e-2 in Random Shooting and Bandit Shooting, and 1c-3 in MCTS and STS), and regularizing, l2 term (weighted by le-6).
of the value function (or the Q-function) loss, the policy loss
pre-trained PPO policy in Shooting methods was obtained using a script included in the Google Research Football repository (see Kurach et al. (2019) and the OpenAl Baselines (Dhariwal et al. (017)) PPO2 implementation.
A.2 HYPER-PARAMETERS
Table 3 presents syper-parametent used in our experiments. These were based on hyper-parameters previously proposed in the literature and substantial amount of tuning experiments (> 3000).
A.3 NETWORK ARCHITECTURES
In GRF experiments we use two different state representations: "simple115" and 'extended" (see Section A.8) In the former case, we use MLP architecture with two hidden layers of 64 neurons, while the latter case, we use 4 convolutional layers with 16, 3x3, filters, zero-pale cero-padding and stride followed by dense layer of 64 neurons. In both cases, two heads, corresponding to value function (or Q-function for MCTS and STS) and policy, follow.
In Sokoban experiments, stride 1, followed by a dense layer of 128 neurons and heads corresponding to a value function and policy (policy is used only for Shooting methods).
5 convolutional layers of 64, 3x3, filters with zero-padding and
In all the cases, we use the ReLU non-linearity. We use the standard Keras initialization schemes, except for MCTS and STS in GRF experiments, Section A.8.2
13

---

Under review as a conference paper at ICLR 2021
Sokoban MCTS
Google Research Football
Parameter
Shooting
STS
Shooting
MCTS
STS
Number of passes C
48
50
10
30
300
30
Planning horizon H
1
10
Discounting ?
0.99
0.99
0.99
0.95
0.99
0.99
0.99
Exploration weight Cpuct
10.0
0.0
0.0
1.0
2.5
1.0
1.0
Policy n temperature*
2.0
2.0
1.0
1.0
Action sampling temp. T
0.3$
0.3
0.3
Dirichlet parameter
0.03$
0.3
0.3
Noise weight Cnoise
0.1
0.1
0.1 / 0.36
Depth limit depth limit?
30
30
VF zero-initializztion
no
no
no
no
yes
yes
Optimizer
RMS
RMS
RMS
RMS
Adam
Adam
Learning rate
2.5e-4
2.5e-4
2.5e-4
1.0c-4
1.0e-3
1.0e-3
Batch size
32
32
32
64
64
64
Target function
rew2go'l'
Iree'l
tree'l'
rew2go'
free'T
free'l'
All y 0.99 except for Shooting experiments with uniform and a pre-trained PPO policy, where 7 0.95.
Applies only Bandit Shooting.
Opuct = 1.0 Bandit Shooting with a uniform and pre-trained PPO policy and Cpuct 2.5 for Bandit
Shooting with trained policy.
Softmax lemperature. MCTS and STS in Sokoban does not use policy, see Section A.5 for details.
Applies only Bandit Shooting with additional exploration mechanisms,, Section A.4
Croise 1.0 STS Conv, and Croise = 0.3 STS MLP.
The maximum number of nodes visited in a single planning pass, see Section A.5
If the last layer of a value function neural network was initialized to 0, see Section A.8.2
Indicates how training targets (CALCULATE TARGET in Algorithm 2 are obtained. rew2goT and treeT corresponds reward-to-ge and "tree action-values" described in Section A.I
Table Default values of hyper-parameters used in our experiments.
A.4 BANDIT SHOOTING
Algorithm 7 Bandit Shooting Planner with additional exploration mechanisms, requires exploration weight Cpuct, action sampling temperature т, noise weight Croise and Dirichlet distribution parameter
function SELECT(state)
function EXPAND(leaf)
state
The same as Algorithn function UPDATE(path, rollout)
P(s, + (1 cnosse) (o + Crosse
(ss, a) t V (ss N(),
The same as Algorithn function CHOOSE ACTION(s) softmmax log (s,,))
+ arg max, (Q(s, Cpuct P ((s,a)
s',r +- model.
return s),
return a
Algorithm 7 describes Bandit Shooting with additional exploration mechanisms: mixing the pol- icy with Dirichlet noise (as in Siilerr al. (2018) and action sampling with temperature in CHOOSE_ (OOOSE__ATIOO())) The noise variable D is sampled from the Dirchlet distribution Dir(a) each time when PLANNER is called (see also Algorithm
A.5 MCTS
In experiments, used various implementations of MCTS. The reasons two-fold. First, some implementation details fit better Sokoban and some GRF. Second, we wanted to check in various cases that the multi-step expansion is beneficial, see (ection[A.6]
In Sokoban experiments, we used the MCTS implementation similar to the one in Milos et al. (2019), containing loop avoidance mechanism and transposition tables. The loop avoidance mechanism
14

---

Under review as a conference paper at ICLR 2021
alters SELECT and CHOOSE ACTION (see Algorithm 5 so that the selected path does not contain repetitions of states. The transposition tables are a rather standard technique, which proposes to accumulate search statistics (i.e., W, .N, Q) for states of the environment (rather than for the nodes of the search tree, as it happens in the standard case).
In GRF, used custom implementation of MCTS based the one in Silver al. (2017). It uses leaf evaluation with Q-function and policy networks. The Q-function is used to evaluate all children of given node once (instead of separately invoking value function Ve in UPDATE). The policy network is considered to be 'prior' for choosing actions, similarly as in SELECT in Algorithm 7 Dirichlet noise, parameterized by a and Cnosse, mixed with the prior in the root and action sampling with temperature т is used to choose action on the real environment, similarly as in Bandit Shooting with additional exploration mechanisms in Section A.4 Additionally, we put a limit, depth limit, t, on the maximum number of nodes visited in a single STS pass.
A.6 STS
We tested STS with two MCTS setups described in Section A.5 substantial experimental improvements as reported in Section A.7 and Section[A, [A.8] This alone, in our view, provides enough evidence that the multi-step expansion is a useful method.
both the cases we observed
Apart from this, STS offers practical computational benefits, which are analyzed below.
A.6.1 COMPUTATIONAL BENEFITS OF STS
We distinguish three types of computational costs in MCTS (see Algorithm 5
Traversing down the search tree (performed in SELECT and EXPAND).
2. Backpropagation of values and counts update (handled by UPDATE).
3. Evaluation of heuristics (value network Vg. or Q-function and policy as described in Section
A.5
In large GRF experiments, we found that it was the first cost that dominated the remaining two. The reason is that the cost of building search tree is quadratic to its depth. The use of multi-step expansion significantly reduces this cost as several nodes are added during single our case, these benefits allowed for much smoother experimenting with GRF and are, arguably, a step towards developing more efficient planners. We expect this might be practically useful (i.e.. costs 1 and 2 are dominant) when the search size is large, or the heuristic evaluation is relatively cheap compared to the environment step. This the case some our GRF experiments. The GRF simulator is rather complex and slower than small MLP networks.
traversal. In
The following simple lemma offers some theoretical analysis.
Lemma A.6.1. Assume that STS and MCTS build the same tree T, starting from the root state su- Denote the number of nodes in T as C and the number nodes to be added at a single multi-step expansion of STS as H. Then the number of steps in T performed by STS will be lower compared to MCTS by a factor in 11-1 b).
Proof. Lets consider consecutive nodes 81.-.., 8h. in the search tree added in a single EXPAND step during STS search. In STS, the number of steps, CSTs, in the tree during SELECT and EXPAND is equal to h+,, where dl is distance between so and 81 in T. To add the same set of nodes during MCTS search, one need h separate calls SELECT and EXPAND. The total number of steps performed is CMCTS Ek- +
hd + h h-1 Clearly,
h
Csrs S CMCTS S hCsrs.
Similar calculation hold for the costs of backpropagation.
15

---

Under review as a conference paper at ICLR 2021
Solved rate
0.4
Planner
MCTS
0.2
STS
Bandit
Bandit with loop avoidance
0.0
200000
400000
600000
800000
1000000
Number steps
Figure 4: Sokoban simpler boards: training curves for MCTS, STS and Bandit Shooting with and without loop avoidance. Mean over 5 seeds with shaded regions representing 95% confidence intervals.
A.7 SOKOBAN EXPERIMENTS
For a description Sokoban see Section 4.1 In our experiments, we used inputs of dimension (z, 2, 7). where (z, z) is the size of the board (10,11) in most cases) and is one-hot encoding of the state of a given cell (enumerated as follows: wall, empty, target, box tt_aaatret box, player, used boxes. The agent rewarded with 1 by putting box
player _argeet) In most experiments, into a designated spot and additionally with 10 when all the boxes are in place") The action space consists of four movement directions (up, down, right, left).
A.7.1 EVALUATION EXPERIMENTS
In Table we show full details of the evaluation experiment (which complements Table Recall that in this experiment, we evaluated the planning capabilities of STS in isolation from training. To this end, we used pre-trained value function and varied the number of passes C' and the depth of multi-step expansion H, such that H C remains constant. In Table we present quantities (Np, Nr, Ng), which measure planning costs for finding a solution (the average number of passes, tree nodes and game states observed, respectively, until the solution is found). We run experiments with and without the loop avoidance mechanism (see Section A.5). spot for the choice of H. It is evident for the 'no avoid loop' case, C 32, H 8. For this choice, the number of tree nodes, Nr, which the most important metric, the smallest. Interestingly, we observe a significant increase in the solved rate. This may be explained by the fact that the number of distinct visited game states, N grows. This suggests that STS explores more aggressively and efficiently. For bigger H. observe further increase of the solved rate until some point, though the cost of much bigger Nr-
observe that there is sweet
In experiments with the avoid loop mechanism, there is similar effect for C' 64, 4, though more subtle, probably because results are already quite strong. Moreover, we observe a more significant drop performance as // increases (when planning resembles more shooting methods).
The values presented in Table 4 are averages over more than 5000 boards.
OOur Sokoban code is fully compatible with Racanière al. 2017).
16

---

Under review as a conference paper at ICLR 2021
Scenario
H
rate
Np
N₂
Ng
256
95.2%
1224
1224
716
128
2
95.9%
569
1137
728
64
4
96.5%
299
1194
830
32
8
95.9%
173
1385
1040
avoid loops
16
16
95.7%
114
1822
1333
32
93.4%
79
2527
1528
4
64
89%
62
3960
1491
128
80%
52.7
6754
1207
256
84.5%
1497
1497
376
128
2
86.3%
724
1448
332
64
4
87.8%
385
1541
370
32
8
88.4%
185
1483
409
no avoid loops
16
16
89.5%
110
1754
539
32
89.9%
84
2690
882
64
85.2%
68
4463
1300
128
65.3%
36
4589
967
Table 4: Evaluation of various STS settings on Sokoban
A.7.2 MCTS AND SHOOTING ON SIMPLER BOARDS
We found the Bandit Shooting method underperforming on Sokoban. As sanity test, we tested simpler setting with smaller boards of size (6, 6) and two boxes. Learning curves are presented in Figure MCTS and STS experiments quickly learn to solve over 99% of boards. Bandit Shooting experiment showed stable
much slower progress. We also evaluated the version of Bandit Shooting, with additional loop avoidance, see Section AA.5, This mechanism was beneficial for MCTS and STS but failed to bring improvements for the shooting algorithms.
A.7.3 CORRECTING BIASED VALUE FUNCTIONS ESTIMATES WITH DEEP SEARCH
To generate value function heatmaps evaluated the pre-trained MCTS value function for each possible agent position in a room. Figures and present two chosen rooms with their corresponding VF heatmaps. Specifically, the room in Figure was solved by the STS with 10 passes and steps of multi-step expansion and wasn't 't solved by the MCTS with 50 passes, both without the avoid loops mechanism. We include movies of both agents this room in the code repository: https: thub. thwb. com/ www.tshoottooooooo treettttreeeeee www.eaacc/stttteeeeeeeeeeeeeeeee httes///teeeemmtteeee///oeeee /movies
Because the value function biased, it makes MCTS stuck in states with overestimated value. See Figure 6 in this room MCTS gets stuck in the bottom-left region. However, with deeper tree, STS can get unstuck quicker and still find solution. Remember that the search statistics (i.c., W, N, Q) accumulated for states of the environment (see Appendix A.5) As this overestimated region gets searched deeper the bias in the value function gets discounted more and the agent figures out there rewards in reality. At some point, other actions will have a higher value and the agent has chance to get unstuck and explore other parts of the room. That being said, it should be noted that this "potential well" will still attract the agent, make its planning paths distracted, even when gets unstuck. STS is less vulnerable to this effect and is able to solve this room despite high bias in the value function.
A.8 GOOGLE RESEARCH FOOTBALL EXPERIMENTS
For a description of Google Research Football see Section A Google Research Football academy environment is considered solved when agent goal. Reported results correspond to solved rates over 20 episodes in case of Shooting methods with an uniform and pre-trained policy and around 30 episodes in case of all other methods. Results for MCTS, STS, and Shooting methods
17

---

Under review as a conference paper at ICLR 2021
XXXX
Figure 5: Sokoban value function heatmap, brighter means higher value estimate.
Figure 6: Sokoban value function heatmap, brighter means higher value estimate.
18

---

Under review as a conference paper at ICLR 2021
with the trained policy medians of at least three training runs. During evaluations disabled Dirichlet noise and action sampling (in Bandit Shooting Expl., MCTS and STS).
Google Research Football offers two major mode of observations: 'simple115" and "extracted" (also called the super mini-map).
The simple1 15 state representation is consists of coordinates of players, planers' movement directions, the ball position, a ball movement direction, a one-hot encoding of ball ownership, a one-hot encoding of which player is active. This totals in a vector of length 115.
The extracted state representation consists stacked layers of size (7). Layers contain one-hot encoding of spatial positions of game entities. These (on the subsequent layers): players on the left team, players on the right team, the ball, and the active player.
We note that even though the extracted representation contains 'less information' than simple1 15, it has been reported in Kurach et al. (2019) to generate better results.
In our experiments, we use the so-called checkpoint rewards, which provide additional signal for approaching the goal area. Details can be found Kurach et al. (2019), where they were introduced and used in large-scale experiments.
The action space in GRF consists of 19 actions representing high-level football behaviors (e.g. "Short Pass"), see Kurach al. (2019) Table 1).
Figure shows training curves for our STS agent on Google Research Football. Training was run for 3 days until convergence. On the y-axis is the solved rate calculated as described above in Section On the x-axis is the number of real steps in the environment (planning steps in the simulator are not added). Curves are mean over training runs with different seeds and shaded regions represent 95% confidence intervals. Moreover, to smooth the curves, data points are averaged in the windows of 10000 steps.
A.8.1 SHOOTING METHODS
Tuning Cpuct turned out to be the most important one make Bandit Shooting work, see Algorithm In nutshell, it needs to be adjusted to scale of rewards (value function) in a given environment. In our experiments we found Cpuct 2.5 to work best.
4
Using additional Dirichlet noise, Cnoise > 0, and action sampling on the real environment, >> 0 (see Algorithm resulted in inferior results with an exception of the "Counterattack hard" scenario.
A.8.2 MCTS AND STS EXPERIMENTS
Apart from multi-step expansion we introduced another simple method, which might be of interest to the general public. Namely, before starting training, we set the weights of the last layer of the Q-value neural network to 0 (see Section A.3 for detailed description of architectures). We observed that this significantly improved the training stability due to better exploration (and avoiding suboptimal strategies at the early stages training). See 'No zero initialization' on Figure [2] This mechanism is
similar to recent recommendations of (Andrychowicz et al. 2020 Section 3.2) given in the model-free setting.
A.9 ABLATIONS AND ANALYSIS
This section is devoted to analysis of various aspects of STS and comparisons MCTS.
A.9.1 ANALYSIS OF THE TREE DEPTH
Recall that hypothesis is that the benefits of multi-step expansion come from tilting the search towards DFS. While it hard to formally prove this statement we were able to pin-point this effect in Sokoban and Google Football experiments, see Figure and Figure Figure@rreppcttvee
19

---

Under review as a conference paper at ICLR 2021
08-
0.-
04
02
0.0
1.0
5001 S00TM
VL with Jeeper
COneer
0.-
0.0
0.0
countoratiack casy
countorattack hard
pass and Shoot With HORDONT
-
0.0
100 200 302 400 500 800 700 800
Number of steps
single
1.0
0.0
0.0
0.4
02
0.0
Mtap
steps
Figure 7: Google Research Football training curves for STS on GRF Mean over 3 seeds with shaded regions representing 95% confidence intervals.
20

---

Under review as a conference paper at ICLR 2021
40
35
30
Average node depth
25
20
15
10
Planner
5
MCTS
STS
0.0
0.2
0.4
0.6
0.8
1.0
1.2
Number of steps
Figure 8: Search depth of MCTS and STS Sokoban.
A&h
HCTV
HCTS
Murbber thaps
Mumber of stot
Figure 9: Search depth of MCTS and STS on three Football Academy tasks.
A.9.2 COMPARISON TO ALPHAGO
We run two additional experiments with rollout-based evaluation using different policies. These meant provide more evidence support hypothesis that the benefit of STS is due the multi-step expansion mechanism.
In each experiment, the rollout was truncated after 10 steps ensure fair comparison with STS. The return after the last step of the rollout was approximated using the Q-value network. This value and rewards collected were used to caleulate the leaf's value in the way in AlphaGo. In experiments, we tested two strategies for generating rollouts:
1. Actions sampled from the prior policy the same setup in AlphaGo, except for rollout truncation and the choice of the policy. AlphaGo used a policy pretrained on expert data. Since do not have access such data for Google Football, instead used the prior policy trained over the course of the algorithm.
2. Actions chosen deterministically. to maximize Q(s, a) + CPUCT (Tals). ). Q was computed by neural network and æ is the probability given by the trained prior distribution. We recall that this setup is equivalent to STS except for the crucial fact that STS adds the expanded leaves to the search tree.
We observed that strategy 1. performed very poorly, which highlights the importance of using neural networks for leaf evaluation. Strategy 2. performed significantly better but still worse than STS. We believe that these results strengthen the evidence that the advantage of STS stems from the algorithmic reasons by building a more efficient search tree. Note the tasks on which the two evaluated strategies performed the worst, i.e. counterattack easy, counterattack hard, single goal versus lazy, are those with the longest lengths of a successful episode. This supports the argument that STS better handles problems with long planning horizons.
21

---

Under review as a conference paper at ICLR 2021
vs. I with keeper
Counterattack
Counterattack
Empty goal
Empty goal close
Pass shoot with keeper
Run pass and
shoot with
Run to score
Run score with keeper
Single goal versus lazy
Method
Comer
easy
hard
keeper
MCTS
Conv.
0.81
0.50
0.31
0.31
0.99
1.00
0.45
0.89
0.70
0.00
0.00
Crnv
0.91
0.09
0.00
0.03
0.00
1.00
1.00
1.00
0.00
0.06
0.00
+d.v.
1.00
0.81
0.06
0.35
1.00
1.00
1.00
1.00
1.00
0.94
0.25
STS
Conv.
1.00
0.81
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.97
0.97
Table 5: Comparison of STS with leaff evaluation using a Q-value network and MCTS with different leaf evaluations: Q-value network only (Conv.), network + deterministic rollout (Conv.td.r.) network + random rollout using the prior policy (C..v.+r.r.). In all experiments we used the same convolutional network architecture. The reported results are the median solved rates across runs.
A.9.3 ABLATIONS OF STS DESIGN CHOICES
The ablations were performed on three environments from GRF Academy: comer, counterattack hard and empty goal, Figure [2 The first environments difficult, while the last one is easy. The following parameters or settings were subject to analysis (they correspond to the labels in Figure 12):
prior noise weight: a weight in the mixture of Dirichlet noise and the prior.
depth limit: the maximum number of nodes visited in a single STS pass.
sampling temperature: temperature for sampling the actions on the real environment.
MCTS n passes 300: this corresponds the standard MCTS setting with
(MCTS)
and C = 300
Value network n papasss: value network is used instead of Q-function. Note that n passes 2 matches roughly the Q-function version in terms of visited states (re- call, see Section that Q-function evaluates all children at once and that number of actions in GRF 19).
No policy: instead of learned policy network, uniform policy is used.
No zero iiitialization the last layer of the value function neural network was not initialized to 0 (see description at the beginning of Section A.8.2).
The default setup (denoted as Prior noise weight 0.1) is always positioned at the top in Figure 12 It uses parameters described in Table 3 in the Google Research Football STS column.
A.9.4 ABLATION BACKPROP WEIGIIT
This ablation aims to verify there is benefit of the aggregate backprop implemented UPDATE in Algorithm 6 We compare the method proposed by Soemers al. (2016), which backpropagates only the last value. We observed a clear advantage of STS on the Sokoban domain, see Figure A.9.4
A.10 MULTI-STEP EXPANSION ANALYSIS ON TOY PROBLEMS
First, consider an MDP presented at the top of Figure II showcases the situation when the enrors are systematic: in the vicinity of the starting state 8p, the estimates of the value function are biased (for simplicity set to and shown as white vertices), while the values in the area surrounding terminal states accurate (shown color vertices). This example is an exaggeration. However, something similar can happen in practice, when information is propagated with -ik-like methods or the environment has "easy" region, which is hard find. Under these circumstances, STS, given large enough H. will be able to reach accurate values (color vertices) within a few passes. On the contrary, MCTS would explore the whole uncertain area (white vertices) in breadth-fin first fashion.
Second, consider an MDP shown at the bottom of Figure II illustrates the case when the emoos are "pseudo-random" In this MDP all rewards 0 except the marked edges, where they are -a, 0.
22

---

Under review as a conference paper at ICLR 2021
1.0
0.8
0.6
0.2
method
simple backprop Soemers (2016)
STS
0.6
1.0
Number steps
Starting from So, the agent can move only to the right. The perfect value function is in every state, however assume that the current noisy value estimates equal to c; the "tail" part of the diagram. In this example, we assume that the errors arise in interactions of many factors, thus can be modeled as i.i.d. centered random variables such that E|c;| +00.
The optimal path, going over the green edge and later over the tail, accompanied by several 'decoy' paths (marked in orange). They will not be entered unless errors the tail have accumulated below such an event by РH, where is the number of steps in the
-a. We denote the probability multi-step expansion (H corresponds MCTS). Lemma A.10.I] we show that p1 pH for H 2 2, and in fact ри - 0 when H + +o0.
Lemma A.10.1. Under the above assumptions pr > pn and pn - 0.
Proof. Assume that for the first 2 2 steps the search tree was unfolded via the middle (green) edge and further via the tail. The state-action value estimated by the MCTS/STS is thus de (co + +... (t22) Consequently,
PH P(RENgии < <)).
The claims follow from the fact qe + a.s., which itself is the consequence of the strong law of large numbers.
As the lemma serves mainly the illustrative purpose we used the i.dd assumption, which can be easily weakened. As test we simulate the case ~ NN 1) and a = 0.3. In this case p1 0.56, P2 0.46, P4 0.35, Ps 0.41, P16 0.21. Note that P1/PH is as high as for
H 16 and quite natural choice of and
A.10.1 HIGH COMPUTATIONAL BUDGETS
STS is predominantly meant to improve the search for modest computational budgets. When the budget gets bigger, any search becomes more exhaustive, and the benefits likely diminish. To our pleasant surprise, see Figure TO we still observe certain advantages of STS in later phases of training, even though MCTS behaves better initially. This observation might suggest another interesting line of inquiry, namely, developing methods for adaptive breadth/depth balancing (c.g. via changing H).
A. INFRASTRUCTURE USED
We ran our experiments on clusters with servers typically equipped with 24 or 28 CPU cores and 64GB of memory. A typical experiment was 72 hours long (the timeout set on the clusters), which was enough for most experiments. Experiments that did converge during this time were resumed.
23

---

Under review as a conference paper at ICLR 2021
ACTS
273 103
20000
60000
10000
100000
000000
100000
020000
20:00
30000
1:300
08:000
U10000
190000
11500
Figure 10: Experiment with big computational budget C 500 on Sokoban.
0.5
Value
-0.5
C0
Figure 11: Visualization of the toy environments.
24

---

Under review as a conference paper at ICLR 2021
weight
Depth limit 100
100%
policy
Value network, n_ passes 30
67 %%
Sampling temperature
644%
Prior noise weight 0.0
78%%
Sampling temperature
No zero initialization
43%
network, nu passes
MCTS papases 300
12%
Depth limit
0%
20%
40%
60%
80%
100%
academy comner
Prior noise weight 0.1
100%
Depth limit 100
100%
Value network, n__ passess 30
100%
policy
93%
Prior noise weight 0.0
600%
Sampling temperature
MCTS n_ pasaessssss 300
56%
Value network, n_
Sampling temperature 1.0
15%
Depth
No zero Inftialization
0%
0%
20%
40% academy_counten howpryyoooottttttt.aarrrr
60%
80%
100%
Prior noise weight 0.1
100%
Prior noise weight 0.0
100%
Depth limi
100%
Sampling lemperature 0.0
100%
Sampling temperature 1.0
100%
MCTS n_ f_passes 300
100%
network, n_ passes
100%
No policy
100%
Inttialization
Value network, n, p_passss2
78%
Depth
0%
20%
40%
60%
80%
100%
academy_emphy wwtpeeepptttp__eeeeeeee
Figure 12: Ablations performed GRF Academy environments: corner, counterattack hard and empty goal.
25


Reviews:
[{"review_id": "vvUx6UGCABv", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 that combines Monte Carlo tree search (MCTS) and random rollouts. The authors their relate this to the bias-variance tradeoff observed in n-step temporal difference methods. The authors evaluate their method on Sokoban and the Google Football League environment. The results show that the authors' method leads to marginal improvements on these domains.\n\nI do not think what the authors are doing is very novel as MCTS combined with rollouts was already used in AlphaGo. Furthermore, I believe the small difference in results can be made up by using only MCTS with a different exploration parameter (i.e. like the one that was used in the AlphaGo paper).\n\nI would like to know what benefits this method brings that cannot be obtained from combining MCTS with rollouts as in AlphaGo or from a hyperaparameter search with MCTS. Is there an anaylsis of the bias variance tradeoff of this method?", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZonZbyneQa5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary:\n---\n\nThe paper presents \"Shoot Tree Search\", an approach that can basically be summarised as a variant of MCTS that expands (adds to the search tree) a longer sequence of up to H nodes to the tree per iteration, as opposed to the standard approach of expanding a single node per iteration. The experiments demonstrate improved performance in comparison to a \"standard\" MCTS and a variety of simpler rollout-based planning approaches, in challenging planning domains such as Sokoban and Google Research Football.\n\nStrong Points\n---\n\n1) Well-written, mostly easy to read and understand.\n2) Simple but interesting idea.\n3) Thorough empirical evaluation, interesting results.\n\nWeak Points\n---\n\n1. The paper describes the modification of MCTS into STS, which consists of making it expand a longer sequence of up to H nodes within a single iteration, as an entirely novel way to extend MCTS, but I'm not sure that that's entirely the case.  For instance, Coulom's 2006/2007 paper \"Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search\" already states: \"In practice, not all the nodes are stored. Storing the whole tree would waste too much time and memory. Only nodes close to the root are memorized.\", which suggests that something like this may have already been considered, but in that case was not found to be worthwhile. The 2016 paper \"Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing\" describes \"In this paper, the tree is simply expanded by adding the whole play-out to the tree.\", which seems similar.\nI do still like that the paper performs a thorough evaluation of this idea, which I am not aware of appearing in previous literature, and the setting with DNNs for value / policy function approximations is also different from aforementioned papers which may lead to different trade-offs. The use of a DNNs for value function probably changes the story quite a bit here, because the longer horizon H also changes the point at which the value function is computed, as opposed to those older papers with values estimated by random rollouts (which remains the same regardless of the horizon H). So I'm not saying the idea isn't \"novel enough\", just that some discussion of past work seems to be missing.\n\n2. In my experience, the primary reasons historically for the typical strategy of expanding just 1 node per iteration in standard MCTS (without DNNs) are 1) to reduce memory usage (especially when copies of game states are stored inside nodes, because then every node can be quite big), and 2) efficiency, because if you store copies of game states in nodes, and create more nodes, you also need to copy more game states (whereas a random playout without node and state storing can just roll out at once without making intermediate copies of states). I'm kind of missing a discussion of these kinds of considerations. \n\n3. I'm not sure that I can fully understand the experiment setup, in particular looking at Table 1. C is a hyperparameter denoting the number of planning passes, and N_p is described as \"the average number of passes until the solution is found\". How can N_p ever exceed C? Shouldn't it be upper bounded by C? I guess C might be the number of planning passes \"per time step\", and N_p is total over the entire episode, something like that? But this is not really clear to me. If the algorithms are really restricted to just C iterations of MCTS, I guess it's fair to always keep C*H constant and then my points above about memory usage / efficiency are not a big deal since they would still be equal across all scenarios... but I'm a bit confused here due to N_p exceeding C.\n\nOverall Recommendation\n---\n\nRight now I have too many little points of confusion / missing discussion, as pointed out under \"weak points\" above, to recommend acceptance. That said, there is also enough to like about the paper, and I can easily envision that most of the points of confusion could be relatively straightforward to clear up in a revision.\n\nQuestions for authors\n---\n\nCould you please clarify on the points raised under \"weak points\" above?\n\nMinor Comments\n---\n\n- On first page, the comma in \"Google Research Football is, an advanced\" seems unnecessary and confusing.\n- On page 6, the wording \"Shooting methods perform poorly for Sokoban\" could be confusing because the newly proposed \"Shoot Tree Search\" method can very easily be interpreted as also being a \"shooting method\" due to its name.\n- In Lemma A.6.1, the assumption that STS and MCTS build the same tree T seems to me like it's a VERY strong assumption; the MCTS has to make very very specific choices, with very frequent overlap making identical choices across different iterations (inherently somewhat unlikely due to the visit count terms in PUCT and other Selection strategies), for this to be true.\n\nAfter Discussion\n---\n\nI increased my review from marginally below to marginally above acceptance threshold. Most of the remarks I had were at least partially addressed. If the paper gets accepted, I'd still recommend looking at some of them again and clarifying more. A simple, explicit remark somewhere around Table 1 explaining that N_p can indeed exceed C due to relevant parts of the search tree being preserved across time steps would help a lot. Some more explicit discussion about why the difference between using a trained value functions vs. heuristics / terminal results matters so much that it makes this substantially different from prior work would also help (I understand that it is because in prior work the only advantage of storing all those extra nodes was really just that it could retain slightly more information from backpropgations in those nodes, whereas in your case it changes which state is the state that gets evaluated by a trained value function, but this should be more explicit in the paper).", "extra_scores": {}, "extra_text": {}}, {"review_id": "WOEvWtzo1h8", "reviewer": "AnonReviewer3", "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": "Summary:\nThis paper proposes a new algorithm named ‘Shoot Tree Search (STS)’ to perform planning in large state spaces. The authors construct STS by redesigning the expansion phase of MCTS using multi-step expansion. The authors provide pseudocode of the STS and compare the performance of STS and MCTS empirically in various domains, such as Sokoban, Google Research Football (GRF).\nComments:\nFirstly, there is no intuitive explanation of why, what and how. Even after reading the paper, I do not agree that STS is good, because there is no intuition as to why it is better than naïve MCTS. More detail, I have a question - The main difference between STS and MCTS seems to be using multi-step expansion or 1-step expansion. Although multi-step expansion will gather more information about (s,a) pairs with high Q(s,a) value (because the actions chosen by argmax Q and STS expands such trajectories), but in sparse reward problem, STS and MCTS will work similarly. Moreover, before getting positive reward, STS may worse than MCTS because it requires more samples to explore (because STS uses more samples for (s,a) pairs with high Q-values, which is not meaningful yet). So I think that this paper needs at least discussion on an intuitive level about the advantage of STS.\nIn addition, the empirical details in appendix (figure 7 and 8 on page 18 and 19, respectively) look weird – each algorithm seems to have stopped randomly or incompletely.\nAlso, the authors seem to need to make an effort to make the paper more self-contained.\nMinor comments\nSome abbreviations are used without its full word or phrase. For examples, MCTS (it has been used in page 1, but the full phrase appears on page 3), and RL.\nThere are no reference for random shooting and bandit shooting. The authors should provide more explanation about them with references.", "extra_scores": {}, "extra_text": {}}, {"review_id": "H9U-XB0g8W", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "summary:\nThis paper introduces Shoot Tree Search (STS), a planning algorithm that performs a multi-step expansion in Monte-Carlo Tree Search. Standard MCTS algorithms expand the search tree by adding one node to the tree for each simulation. In contrast, the proposed STS adds multiple nodes to the search tree at each simulation, where each node corresponds to the state and action that are encountered during rollout. By multi-step expansion, the evaluation of the trajectory is less-biased, which can be analogous to n-step TD. In the experiments on Sokoban and Google research football domains, STS outperforms baselines that include Random shooting, Banding shooting, and MCTS.\n\n\nOverall, my main concerns are technical novelty and presentation quality.\n\nThe most common MCTS methods assume that the leaf node is expanded one at a time in each simulation (and its evaluation is performed either by rollout policy or by function approximator), but this common practice does not necessarily mean that MCTS should always do that. The main reason for only expanding one node per simulation in standard MCTS is memory efficiency: if we fully expand the rollout trajectory and retain its information to the search tree, we may get slightly more accurate value estimates. However, the nodes located deep in the tree will not be visited more than once in most cases, thus its effect is usually not significant, leading to the common practice of one-step expansion. More importantly, multi-step expansion has already been used in existing works (e.g. in [1], the tree is expanded by adding the whole rollout trajectory), thus I am not convinced that this work introduces a technical novelty.\n\nIt seems that the relative benefit of the STS over MCTS observed in the experiments comes from the bias of the value function approximator. However, to show the effectiveness of 'multi-step' expansion compared to 'single-step' expansion, I think that more thorough ablation experiments should have been conducted. For example, we can consider the setting where both STS and MCTS perform leaf-node evaluation (i.e. UPDATE in Algorithm 5) by executing rollout policy rather than by using value function approximator. By doing so, we can focus only on the benefits of STS's retaining information of full rollout trajectory (i.e. multi-step expansion), compared to MCTS's retaining one-step information (i.e. single-step expansion) while eliminating the effect of biased value function estimation.\nTo relieve too much bias in the current MCTS's leaf node evaluation, mixing MC return of rollout policy and the output of the value network could also have been considered, as in AlphaGo (Silver et al. 2016). It would be great to see if STS still has advantages over MCTS in various leaf node evaluation situations.\n\nAlso, more writing effort may be required, and the current version of the manuscript seems premature to be published. There are some unclear or questionable parts.\n- Algorithm 3 and Algorithm 4 are not the contributions of this work, thus they can be removed or moved to the Appendix. Instead, more discussions regarding the proposed method should have been placed in the main text.\n- In Algorithm 2: the definition of CALCULATE_TARGET is missing.\n- In Algorithm 5: In SELECT, the tree policy is defined by CHOOSE_ACTION that selects purely greedy action. If this describes the MCTS used in the experiments, I would say this is wrong. To make MCTS be properly working, an in-tree policy that balances exploration vs. exploitation is required (e.g. a classical choice is UCB rule).\n- In Algorithm 6: In UPDATE, $N(s,a)$ and $quality$ are increased by $c$ times more, which means that the longer rollout length, the more weight is given. What is the reason for assigning more weight to the trajectory that has a longer rollout length? If the entire planning horizon is limited to finite length, this means that early simulations (short $path$ length, long $rollout$ length) have more weight than later simulations (long $path$ length, short $rollout$ length), but I do not think this is desirable. Is my understanding correct?\n- For the Sokoban experiments, the pre-trained value function would significantly affect the performance of MCTS and STS, but I could not find the way how the value function was pre-trained.\n- In Appendix A.2., the hyperparameters for Shooting and STS are very much different. Why did you set Shooting's hyperparameter differently from STS (e.g. VF zero-initialization, action sampling temp, etc.)?\n- It seems that the choice of zero-initialization of the value network is rather arbitrary. I am not convinced that this would always work better. In some situations, optimistic initialization of the value network may be helpful to encourage exploration of the uncertain state regions.\n- In Table 2, Why does RandomShooting-PPO underperform PPO? Since RandomShooting-PPO puts additional search efforts upon PPO, I expected that RandomShooting-PPO must outperform PPO.\n- Table 5 could have been moved to the main text, replacing Table 2.\n\n[1] Soemers et al., Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing, 2016 IEEE Conference on Computational Intelligence and Games (CIG 2016)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2CSPQtGSJsB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "**Summary**\nThis paper presents a new planning algorithm, called Shoot Tree Search, to control the trade-off between depth and breath of the search. STS modifies the expansion phase of tree search by choosing multiple actions (e.g. $\\gt$ 1) instead of one level expansion. The presented idea is simple and straightforward and seems to provide improvement over existing tree-based planning algorithms. The presented detailed ablation studies provides insights about the choices made in the paper. \n\n**Reasons for score**\nOverall, I liked the paper and the simplicity of the idea. However, my major concern is the comparison with MCTS. I am not convinced that STS would outperform vanilla MCTS when the number of simulations is in order of thousands (e.g. the number of simulations in AlphaGo paper is around 1600). \n\n**Strengths**\n+ The idea is simple and seems to outperform vanilla MCTS implementation in the environments with large action space.\n\n**Weaknesses**\n+ The comparison with the related work is not thorough which makes it hard to come into a decisive conclusion about the performance of the proposed method.\n+  There are some missing related work, e.g. using policy network for multiple rounds of simulations.\n\n**Questions**\n+ What would the benefits if we have a policy network to perform the rollouts (e.g. a similar method to [1])?\n+ In general, the benefit of MCTS algorithm (like AlphaGo which performs around 1600 simulations) presents itself when the number of simulations are large. Can you compare running MCTS with more number of simulations (e.g. large C) and STS?\n+ Can you please provide some insights on why in 'Corner' STS underperform compared to random shooting?\n\n[1] https://cs.brown.edu/people/gdk/pubs/analysis_mcts.pdf", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a modification to MCTS in which a sequence of nodes (obtained by following the policy prior) are added to the search tree per simulation, rather than just a single node. This encourages deeper searches that what is typically attained by vanilla MCTS. STS results in slightly improved performance in Sokoban and much larger improvements Google Research Football.

R4 and R1 both liked the simplicity of the idea, with R1 also praising the paper for the thoroughness of its evaluation. I agree that the idea is interesting and worth exploring, and am impressed by the scope of the experiments in the paper as well as the additional ones linked to in the rebuttal. However, R1 and R5 explicitly noted they had many points of confusion, and across the reviews there seemed to be many questions regarding the difference between STS and other variants of MCTS. I also needed to read parts of the paper multiple times to fully understand the approach. If this many experts on planning and MCTS are confused, then I think readers who are less familiar with the area will definitely struggle to understand the main takeaways. While I do think the clarifications and new experiments provided in the rebuttal help, my overall sense is that the paper at this stage is not written clearly enough to be ready for publication at ICLR. I would encourage the authors to try to synthesize their results and organize them more succinctly in future versions of the paper.

One comment about a point of confusion that I had: I noticed the PUCT exploration parameter was set to zero for Sokoban, and one for GRF (with an explanation given that many values were tried, though these values are unspecified). As the exploration parameter is normally considered to be the thing that controls whether MCTS acts more like BFS ($c = \infty$) or DFS ($c = 0.0$), I would encourage the authors to more explicitly report which values they tried and to be clearer about the advantage of STS's multi-step expansions over low values of the exploration parameter.
Decision: Reject