A⋆MCTS: SEARCH WITH THEORETICAL GUARANTEE USING POLICY AND VALUE FUNCTIONS
Authors: Xian Wu
Yuandong Tian
Lexing Ying
Venue:  (2020)
Keywords: tree search
reinforcement learning
value neural network
policy neural network

Abstract: Combined with policy and value neural networks, Monte Carlos Tree Search (MCTS) is a critical component of the recent success of AI agents in learning to play board games like Chess and Go (Silver et al., 2017). However, the theoretical foundations of MCTS with policy and value networks remains open. Inspired by MCTS, we propose A⋆MCTS, a novel search algorithm that uses both the policy and value predictors to guide search and enjoys theoretical guarantees. Specifically, assuming that value and policy networks give reasonably accurate signals of the values of each state and action, the sample complexity (number of calls to the value network) to estimate the value of the current state, as well as the optimal one-step action to take from the current state, can be bounded. We apply our theoretical framework to different models for the noise distribution of the policy and value network as well as the distribution of rewards, and show that for these general models, the sample complexity is polynomial in D, where D is the depth of the search tree. Empirically, our method outperforms MCTS in these models.

Under review as a conference paper at ICLR 2020
A'MCTS: SEARCH WITH THEORETICAL GUARANTEE USING POLICY AND VALUE FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Combined with policy and value neural networks, Monte Carlos Tree Search (MCTS) is critical component of the recent success of Al agents in learning to play board games like Chess and Go (Silver et al. (017). However, the theoretical foundations of MCTS with policy and value networks remains open. Inspired by MCTS, we propose A MC7S, a novel search algorithm that uses both the policy and value predictors to guide search and enjoys theoretical guarantces. Specifically, assuming that value and policy networks give reasonably accurate signals of the values of each state and action, the sample complexity (number of calls to the value network) to estimate the value of the current state, well the optimal one-step action to take from the current state, can be bounded. We apply our theoretical framework different models for the noise distribution of the policy and value network as well as the distribution of rewards, and show that for these general models, the sample complexity is polynomial in D, where D is the depth of the search tree. Empirically, our method outperforms MCTS in these models.
INTRODUCTION
Monte Carlo Tree Search (MCTS) is an online heuristic search algorithm commonly used to find op- timal policies for problems in reinforcement learning. It is vital component of recent breakthroughs for Al game play, including AlphaGo and AlphaZero (Silver et al. 2016 2017).
An interesting difference between the MCTS used in AyphaGo/AllpaaZan the adoption of neural networks to predict the value of the current state (value network), and to prioritize the next action to search (policy network). The value network replaces random rollouts used to evaluate a non-terminal state, which saves both online computation time and substantially reduces the variance of the estimate. The policy network (coupled with PUCT (Rosin 2011) prioritizes promising actions for more fruitful exploration. Both networks are trained on pre-existing datasets (either from human replays or self-play) to incorporate prior knowledge. This strategy has been applied in other domains including Neural Architecture Search (Wang et al. 2018: Wistuba 2017
and traditional MCTS
Negrinho & Gordon 2017:
Wang al. 2019b).
Despite the empirical success and recent popularity. theoretical foundations are lacking. (oocsis & Szepesvári 2006 Coquelin & Munos| 2007) analyze MCTS with rollouts using multi-armed bandit framework and gives asymptotic results without finite sample complexity bounds. Powering MCTS with value/policy neural networks instead of rollouts is even more poorly understood.
To better understand how to efficiently learn optimal policies in decision trees using value and policy networks. we propose a novel algorithm, A ACMSS, which is a combination of A (Delling al.) 2009 Kanoulas et al.) 2006) and MCTS. Like A", it uses priority queue to store all leaves currently being explored and picks the most optimistic one to expand, according to an upper confidence bound heuristic function. Like MCTS, it uses policy and value networks to prioritize the next state to be explored.
To facilitate the analysis, the policy and value networks are treated as black-box functions and sta- tistical model built the accuracy of the predictions. In particular, we assume the standard deviation of the noisy estimates of intermediate state values decays (either polynomially exponentially) function the depth of the tree, so that the values near-terminal states are estimated to a greater degree of accuracy. With this statistical model, we provide theoretical guarantees for the sample

---

Under review as a conference paper at ICLR 2020
complexity (expected number of state expansions / rollouts) to determine optimal actions. We apply our theoretical framework to simple models for rewards and show that our algorithm enjoys a sample complexity that is polynomial in depth D.
Our experiments validate the theoretical analysis and demonstrate the effectiveness of 4CMCSS over benchmark MCTS algorithms with value and policy networks. To our knowledge, our work is the first that studies tree search for optimal actions in the presence of pre-trained value and policy networks, and we hope that it inspires further progress on this important problem.
2 BACKGROUND AND RELATED WORK
Monte Carlo Tree Search (Browne et al. 2012) is an algorithm that tries to find optimal decisions in Markov Decision Processes by taking random samples the decision space and building a tree based on the results. In each iteration, the agent traverses the tree by acting according to the tree policy (which usually involves some exploration) for the set of known states and then determines the value of an unexpanded state by performing random rollouts.
MCTS commonly used to search for a one-step optimal actions from the root. The agent then takes this action, observes the result, transitions new state, with the benefit of the additional observation. The main theoretical question of interest in MCTS is how quickly and efficiently one can find this optimal one-step action, in terms of the number of random rollouts, or the number of nodes the tree that should be expanded. On the theoretical side, there is small body of literature that addresses the theoretical foundations of MCTS with random rollouts (Koesis & Szepesvári (2006). Veness et al. 1))1 The algorithm, called complex multi-armed bandit problem where the
new state, and repeats MCTS starting from this
UCT (UCB applied trees) models the search rewards are allowed to drift over time. The analysis shows that after a period of time T. only the optimal branch will be followed. |ennes et al. (2011) gives various ways of improving UCT with variance reduction techniques.
Later followup work in Coquelin Munos 2007) highlights some hard instances of UCT and offers some alternatives, including a modified UCT (with a different exploration bonus), Flat UCB, and BAST (smooth tree models).
On the experimental side, MCTS was popularized by the story of AlphaGo (Silver et al. (2016)) which used MCTS using weighted combination of the value network's 's output and random rollouts to defeat the leading champion in Go. Follow-up work in AlphaZero (Silver et al. (2017) used MCTS with only policy and value neural networks, without random rollouts and reports faster training with better performance. However, there is no theoretical foundation for the search algorithm that AlphaZero uses.
A (Nosrati et al., 2012) uses a priority queue to keep track of lowest cost actions. A" combined with hand designed heuristics, has been used in many path finding and routing problems (AlShawi et al.
2012 Rana & Zaveri 2011 1 Ghaffari 2014). Recent work (Wang et al., 2019a Chen & Wei| 2011 Sigurdson & Bulitko, 2017) trains neural-based heuristic functions for A for specific problems. However, the best of our knowledge, are not aware of any prior work that performs theoretical analysis of such heuristic based A algorithms.
PRELIMINARIES AND SUMMARY OF CONTRIBUTIONS
In this work we consider a deterministic, finite D-horizon Markov decision process (MDP) with no intermediate rewards. With the set of states denoted by S, there is one deterministic root initial state so and the process terminates horizon with a termination reward that depends on the end state. We assume that there exactly K possible actions at every intermediate state s and for simplicity that the process does not backtrack, i.e., each action leads to a new and unique state. This is a Markov decision tree.
The set of leaf states of the Markov decision tree are denoted as L. We shall denote an arbitrary state depth d sa and also leaf state as / E L. There is value function V : S + R that takes as input a state s and returns the value of s, defined in the following way. If s E L. then V, is the termination reward of that particular leaf. For intermediate node V. maxie Vi, where
2

---

Under review as a conference paper at ICLR 2020
Summary of Notations Used
K
Branching factor
Vas
True value of state sa at depth d
Asg
Gap to optimal value (V* Vs.)
Usa
Predicted value of state sa by value network (deterministic)
Xd
O-mean, standard deviation aa random variable for the noise of the value prediction Us, at depth d. Vs, UsR Xd. standard deviation of Xx. fixed and known as part of the problem model.
aa
We assume that ay decays with depth.
ca
exploration bonus, determined based Øg. X ca with high probability
Usg +
priority value (value used to determine the ordering of which to nodes expand in the priority queue).
U
Predicted value of child i some depth d by policy network (deterministic) O-mean, standard deviation dd random variable for the noise of the value prediction of child at depth d, U.. V,, U.. X2.
X
Table Summary of main notations used in the paper.
((s) the set of leaf nodes that share s as an ancestor, i.e., the set of leaf nodes the subtree rooted at We assume that the highest value V* = maxiec Vi2 max,es V. is achieved at unique leaf node 1" = arg maxtec Vi.
In this work, focus the problem of efficiently computing V exactly or approximately with controlled accuracy without direct access to the value function V S + R. as a stepping stone to finding the optimal one-step action from Sp. Instead, there is pre-trained black-box resource, value network U S + R that takes as input a state and returns a noisy value estimate, i.e., for a state sa at depth d. U., = V + Xay. where X,, are i...d. copies of random variable X,, that depends only on the depth d. We assume that at depth D, which is the level with all the leaf nodes, Uj = Vi (i.e., the value network returns the ground truth values without any noise). The efficiency is defined in terms of sample complexity, which is the number of queries made to the value network for the value of state. In the worst case, all leaves need to be queried and the sample complexity is K
Another type of available pre-trained black box resource is policy network. Let Css) {ri,... .Tk. denote the set of K children of state s, each corresponding to the transition state of one of the K
actions {a1 lt....ac .xka [ukk The policy network outputs a probability estimate of the form Pr. ΣK_ "
where each U is a perturbed estimate of Vr.. Here the superscript и indicates that this is the approximation from the policy network. We assume that if the child is depth d then the estimate U.. = Vr; + X where X are i.i.d. copies of random variable X that depends only on the depth d. We assume that the distribution of Xa and X3 are known priori for each depth d. Further. the variances of Xa and X decrease sufficiently rapidly as the depth d increases (i.c.. as one traverses deeper in the tree, the noise level smaller). This assumption is motivated by basic approximate dynamic programming principles, which is that near- near-terminal states require smaller sample complexity to estimate well, since the backwards induction will propagate this noise to earlier states, making it harder to estimate the values of initial states well.
3.1 MAIN CONTRIBUTIONS
We develop and analyze (giving specific sample complexity bounds) algorithms to estimate V* exactly and approximately using value and policy networks. Since our value and policy networks are trained functions that give fixed, deterministic noisy outputs for each state (no matter how many times one calls the function on a particular state), where the noise variance is smaller at deeper levels of the search tree, we use our value and policy network estimates as signals for which are the promising states to expand. We rank the states based our optimistic estimates U., Ca in a priority queue, and we expand (query the value network for the value estimate) the children of the top nodes of the priority queue to get increasingly more accurate value estimates and determine the value of the optimal leaf V*
The main contributions are organized in the following sections:
3

---

Under review as a conference paper at ICLR 2020
Section introduces and analyzes A'MCTS-V* and A*MCTS- V that are techniques for estimating V exactly. A*MCTS-V' V uses only a value network to determine V exactly and outputs the optimal one-step from so that leads to 1*. We give expected sample complexity in Theorem A M"MCTS->"VV builds on A MCCTS-V* by using policy network further reduce the sample complexity, which bound in Theorem
Section A MCTS-V" and A 4'MCTS-T'V' to the case when we tolerate ò-additive approximations of V*
Section 6 introduces some sample distribution models for the value functions and the noise and applies our results to those models. We show that for some reasonable models, our algorithms can achieve sample complexity that is polynomial in depth D. We also provide some experimental comparisons against benchmark MCTS implementations.
4 FINDING V* EXACTLY USING VALUE AND POLICY NETWORKS
This section presents our main techniques, A A'MCTS-V* and A' A'MCTS-='V' which find V exactly using a value network only in the former and value network and policy network in the latter.
A*MCTS-V* Algorithm [ uses only a value network to determine V exactly and outputs the optimal one-step action from 8o that takes the agent to ancestor of l". The idea behind the algorithm is very simple and similar to A" search. We first expand (i.e., query the value network) the children of the root node 8o. compute their value network estimate plus the exploration bonus, and then insert these nodes to priority queue Q. The exploration bonus, denoted by ca. is chosen such that P([V., Uzal I ca) 2 1 DK*- In each subsequent iteration, the algorithm picks the top element in the priority queue Q. which is the most optimistic state, and expands all the children of that state, and adds those children to Q. We terminate at the first time when the most optimistic element a leaf node. Since the value network gives the values of leaf nodes exactly, this leaf node must be !*.
Prioritize node using value model
Next eepand
Priority Queue
Expand nade using policy model
Figure 1: Illustration our overall method. We prioritize nodes to expand using the value network estimates. Algorithm D queries the value network for all children of the first node in the priority queue. our next algorithm, Algorithm(2 [ we show how to use a policy network to choose which children nodes to add to the priority queue.
We present the complexity bound in Theorem The complexity bound is based one very simple observation, which is that we end up choosing a sub-optimal node if the value network estimate of that node plus the upper bound on the possible error (optimism) is higher than the true optimal value. Otherwise we will not choose to expand that node, since we are sure that it will not be the optimal node. Therefore sub-optimal internal node sa chosen if V S U., + Ca = Vs, + +X,, + Ca, where Un, is the value network estimate for state s,, and is the upper bound on the possible error for the value estimate. We should also account for the ancestors s,, if we are lucky enough to be able to rule out one of the ancestors of sa, would never expand beyond that ancestor reach sa, and sa would not be in our priority queue. Theorem T states this complexity bound.
Theorem 1. With probability complexity (number of calls to the value network) is
Algorithm 7 A ACMTSVV returns V*. The expected sample
E| KD+
Σ
K.P
A - -x. cdl 50
Dew Xoy cd' 50
ecES (EES.eaEC.
EA(oa)
4

---

do not have to Under review as a conference paper at ICLR 2020
Algorithm 1 MCTS-V
Require: Value Network with error distribution for Xa at each depth d S D
1: For each d < D, compute so that PP( S ca) 2 1 DK
2: Q f- (so: U' + ca)
3: while the depth of Q.front() is do
4:
=Q.pop()
5: f do
6: d f depth of
7:
Q.enqueue U, + ca) 8: end for
9: end while
10: (s.-) Q-front()
11:
Return Ug and the action at So that leads to $
where A(I)) the set of ancestor states of the optimal leaf. 1*, and D.. V Vss-
Before we give the proof, we briefly note that getting an exact expression for the expected sample complexity depends on the problem model (the distribution for the gaps AsN and the errors X. We give two examples in Section of different models and we apply this theorem to those models to derive the sample complexity, which we show is polynomial in depth D. Please check Appendix for the proof.
4.1 COMBINING VALUE NETWORK WITH POLICY NETWORK
Suppose that in addition to the value network U, one has access policy network U that outputs, for each child of s, ri,... .K (each corresponding to the transition state of different action a1.... ..) a probability estimate the form:
Pr. kk=1
where each U Vr + X is perturbed estimate of Vr,, If r. is depth d the noise X is an i.i.d. copy of the random variable X, that depends only on the depth d. Since all the probabilities are known, we assume without loss generality that states r..... TK are ordered so that U, 2 U. 2 U
U or equivalently Pr, 2 Pra 2 Pra
Prx
The following algorithm A'MCTS-T" uses both the value and the policy networks determine V exactly. When we expand given state sa. instead of querying for the value estimate for every child of 8a and adding each child the priority queue, we add the top 2 children (ordered by the probabilities given by the policy network) to the queue by default. For the k-th child node, where 2, we add this child if there a small gap between the policy network probability of the k 1-th child and the probability of the top child, where the threshold for the gap given by the noise model. Intuitively, we are saying that if this gap sufficiently big, even after accounting for the noise in the policy network, there is no way that this k-th child is part of the optimal policy, add it to the queue.
The key insight behind this algorithm is that, if there is large gap between the probabilities of the children as given by the policy network, one can infer that the children states associated with the not worth expanding because they have small values. This is made rigorous
smaller probabilities in the statement and proof of Theorem 2
Theorem 2. With probability
Algorithmm 2 A'MCTS- V returns V The expected sample
complexity (number of calls to the value network) is
K
- Vra + ( - (atza, S 22 22...1)
EMM E
2
PP
Vr,
2=
P
A
X1,
Cd 50
Aag Nzg. ca $0
Sur EA(sa)))
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 *
Require: Value Network, Policy Network, failure tolerance 3 I ca) 2
1: For each d < D, compute so that IP( Xal
2DK 2: For each d D, compute cj so that P( - c 2 2DK4
Q t- (s0, U+a)
4: while the depth of Q. Q.fron(() is < do
5: (s, - = Q-pop()
6:
for [1...., K], ordered according to the probabilities of the policy network do depth rf
7:
8:
if or In
Pri I 2cd then
Pr.-1
9:
Qenqueue (r,, Ur, ca)
10: else
break:
12: end if
end for
14:
end while
(s, ) Q-front()
16: Return U, and the action at that leads to
where Dr, V+ Vag and X (a+1), the random variable associated with Tk for the policy network, i.e. U = Vr, + (d+1),
As with Theorem getting an exact expression for the expected sample complexity depends on the problem model (the distribution for the gaps As, and the errors Xsy). We give two examples Section 6 of different models and we apply this theorem to those models to derive the sample complexity, which we show is polynomial in depth D. Please check Appendix for the proof.
APPROXIMATING V* USING VALUE AND POLICY NETWORKS
This section extends the algorithms to the problem setting where we are willing tolerate an additive error ó in the estimate for V*
We first consider the extension of A*MCTS-V* Algorithm | The key idea is that suffices to stop searching at a depth D whenever Cp & 5. As long as the most optimistic state at depth D is identified, the value of this state approximates V up additive enror 5. The main result is stated in Theorem 3 and the algorithm Algorithm A MCTSS-, presented in Appendix 8.3
Theorem 3. With probability 1 3, Algorithm 3
ACMCSS-V returns V* up additive error 8. The expected sample complexity (number of calls to the value network)
B[ KD+ Σ K.P.
Aoj -X,, - Ga CD 50
n
Day Xay - cx 50
BAES d<D &d(A((!))
Sy E(A(s))
where A(l)) is the set of ancestor states of the optimal leaf, 1", and Dag = V* Vap and D is the minimum depth at which cp E
Using the same reasoning as the one for A*MCTS- we can extend 4*MCTS-T" V to the following result.

---

Under review as a conference paper at ICLR 2020
Theorem 4. With probability 1 B, one find V up additive approximation ervor ó using expected sample complexity (number of calls to the value network):
K
11at11, S 20h11)
E|
S
Σ
2+
Σ
Vr + (dt1i) +X Vn
sa,deD
2=2
P
Dos
Xea
Cd
C 0
Dey Xoy -c8 cD S
(((sa)
where is the minimum depth at which cp 2 6.
6 MODELS AND EXPERIMENTS
In this section, we discuss two simple yet representative models for the Markov decision tree and show that the sample complexity polynomially bounded under reasonable noise models.
6.1 CHOOSING ca FOR GAUSSIAN NOISE
The noises Xa, X are taken to be Gaussian (0, random variables. Two noise models are tested. The first is Gaussian with an exponentially decaying standard deviation, i.e., X X ~ NN qua) for some a > 1. The second is a Gaussian with polynomially decaying standard deviation, l.e., Xa, XI ~ (0, Z ) for some 7 > The experiments are carried out for a 1.3 and 1.5 for the exponential case and y = 1.3 and 1.5 for the polynomial case.
The assumption of decaying standard deviation as a function of depth motivated by basic approxi- mate dynamic programming principles, which elaborate in Section
The choice of ca is essential to the performance of the algorithms. Standard concentration inequalities
for nub-Gaussian random variables state that P([Xal 2 ca) 2c अس and this probability expression required to be less than DK After substituting it in, arrive ca O O(ydoa).
6.2 CONSTANT GAP MODEL
In the constant gap model, V - Vi- 1 for fixed constant r and Vi 0 for any other leaf 1 + 1 Therefore, the gap A()) for any * 1" The noise variables Xa, X7 are mean-zero Gaussian random variables.
V' 0
v(sa) 0
0
0
0
O0
O
0
O 1 00
Figure 2: The constant gap model. The leaves have value 0 except for the optimal leaf, which has value 77. blue path a sub-optimal path, the red path is the optimal path.
Using value network. The expected sample complexity for Algorithm iis
D-1d-1
E = KD +
Σ
Σ
(K- - 1) II KP(n X(d-i) ((d-)) S
d= 2=
==0

---

Under review as a conference paper at ICLR 2020
This translates to sample complexity of E[N] KD D2 - 1)K2, for the smallest constant that satisfies 3. vc 2 V2log K.
The analysis for this result, as well as similar analyses and sample complexity results for Algorithm and the approximate counterparts are in Appendix 88.4
Experiments. We compare the performance of A' MCTSS- with the MCTS algorithm that uses the UCB estimate Qs,a + / 1 N..a) with random rollouts, where is a constant, and N&. are visitation counts for choosing action from state s. We also compare A*MCTS- with the PUCT algorithm described in Silver et al.
and queries the value network U, instead expanding state
No.a
(217)) that uses the UCB estimate Qs,a + c Ps.a Σ. Noa the policy network U
where Ps,a is the probability given by Nx,a
The experiments are performed on tree of depth in the constant gap model, the optimal leaf has reward and all other leaves have reward O, and we experiment with 7 = and r) = 0.5. In our experiments, we use c = 1 in the the bonus UCB expression for benchmark MCTS and PUCT algorithms. Our algorithms set Ga = 5 vda,, where aa is the variance of the Gaussian noise. This choice is justified carlier in Section 6.1
10 with K children per state. As defined
Since the main use case for these algorithms is to find the optimal one-step action from so, we collect data on the one-step action that the algorithm would output every 1, 000 expansions (or queries to the value network U). MCTS algorithms would output the one-step action from so with the highest visitation count. Our algorithms would output the action from sq that leads to where the highest-valued element in the current priority queue Q based on the value network estimate U.- We give overall budget of 20,000 expansions and note whether not (so the data is 0) the algorithm chooses the right one-step action. Each of our experiments average over 200 trials. Tables I aand 2 give the proportion of trials that return the correct optimal one-step action at the 20.000-th expansion. To give an idea about the performance gain, Figures 3 andd show the success proportion over time, at successive 1000 expansion intervals for Algorithm and PUCT for 0.5 both noise models (polynomially and exponentially decaying).
Polynomially Decaying Noise
Exponentially Decaying Noise
1.3
1.5
1.3
1.5
Alg
MCTS
Alg
MCTS
Alg 1
MCTS
Alg
MCTS
17
0.51
0.695
0.355
0.605
17
0.5
1
0.38
1
0.435
0.65
0.265
1
0.4
Table 2: Value Network Only Results for the Constant Gap Model
Polynomially Decaying Noise
Exponentially Decaying Noise
1.3
1.5
1.3
1.5
Alg
PUCT
Alg
2
PUCT
Alg
2
PUCT
Alg
2
PUCT
0.5
0.885
0.92
0.685
.705
0.875
Table 3; Value and Policy Network Results for the Constant Gap Model
6.3
GENERATIVE MODEL
The model generates the value function of the nodes in the Markov decision tree in a recursive way. This model first chooses the optimal value Va,, V* at the root 8n- Given the value function of parent node p, the value functions for the children . are generated as follows: one of the children (without loss of generality, say r1) has the same value function as the parent Vp, each of the remaining children r; has a value function Vp - Y with Y sampled independently from [O, ny]. the uniform distribution over the interval [0, v). At level d, there are exactly (:) (K - 1)a states with value function distributed according to V (Yr +... ....... Y,). When is negneggli,,,,, Yi +... Y concentrates constant value 2 by the concentration of measure phenomenon.
8

---

Under review as a conference paper at ICLR 2020
Value
polyconially
Value Coustant Madel expcreatialy
Optical
oferr
62-
42-
ge ponna
A aptam
355
15.0
175
303
150
175
Narber
Narber
Figure 3: Using Value and Policy Networks for search in the Constant Gap Model with polynomially decaying noise and r) = 0.5.
Figure 4: Using Value and Policy Networks for search in the Constant Gap Model with exponentially decaying noise and ry = 0.5.
A U[O.1] n]
O y" - Ó
V' V
V
V"
4
42 4
Figure 5: The generative model. A blue path is sub-optimal path, the red path is the optimal path. The optimal leaf has value V* Sub-optimal nodes inherit the gaps their parent as well as an extra gap Y. that the sub-optimal leaf values get smaller and smaller.
Using value networks. Following the estimate in Theorem the overall complexity for Algorithm 1 can be bounded up to an extra KDD term by
ΣΣ (k 1)'P Xa
Tpl 2
>>
11'P 2 (2))())))))
d (K-
-övd
Ca
20a
d=1
where Z is a standard normal distribution. The goal to bound this by quantity polynomial (rather than exponential) in D when 1), K, and a are considered fixed. To proceed, we introduce T(d)= 2ov2log k+1)/k
For any t 2 T(d).
nt 2
εva) S e log
log Kd
K-d.
20
Therefore, for a fixed d,
Σ (KK--))p 2
nt
ovd < Σ (2) (DK--IJK-
(10
Σ
(K-I
20a
t= T(d)
T
Therefore, up to term linear in D, the sample complexity can be bounded by
D T(d)
ΣΣ
( (K- (K - 1)'P
1)'P
ne
ōva
(1)
2
Notice first that P(Z > and polynomial noise models aa decays faster than 1/ V/ asyptotiically T(d) 2( log K+1)/daa
mt 20
V is always bounded by 1. Second, since in both the exponential

---

Under review as a conference paper at ICLR 2020
is uniformly bounded by constant C(K, 17, a) due to the exponential decay in d. Therefore, the term (4) can be bounded by (DK) (DK)C(K)).)) which is polynomial (rather than exponential) in the depth D.
Similar analysis and sample complexity statements can be made for the performance of Algorithm and the approximate counterparts. We defer this treatment to Appendix 8.3
Experiments. Our experimental results for Generative Model follow the same setup and parame- ters as the experiments for the Constant Gap Model in Section 6.2 Tables give the proportion of trials that return the correct optimal one-step action at the 20,000-th expansion. Figures and show the success proportion over time, at successive 1000 expansion intervals for Algorithm 2
and
PUCT for y = both noise models (polynomially and exponentially decaying).
Polynomially Decaying Noise
Exponentially Decaying Noise
1.3
1.5
1.3
1.5
Alg
MCTS
Alg
MCTS
Alg
MCTS
Alg 1
MCTS
0.895
0.895
0.9
0.895
= 0.5
0.865
0.865
0.825
0.865
0.995
0.87
Table 4: Value Network Only Results for the Generative Model
Polynomially Decaying Noise
Exponentially Decaying Noise
1.3
1.5
1.3
1.5
Alg 2
PUCT
Alg
2
PUCT
Alg
2
PUCT
Alg
2
PUCT
17
0.94
0.94
0.99
0.92
0.935
17
0.5
1
0.935
1
0.92
0.82
0.9
1
0.92
Table 5: Value and Policy Network Results for the Generative Model
Volue and Palicy Geandiiee wtw.aaaaaddppaaaaannioiii polpaunially docuying
Valaz Polky Gaazn exgenctially decaping
Proveter Ove
0/-
06
FUCT with prmne
PUCT wihiiblo 11
A"MACTSge""" "V with panna
A" wilk aplu 13
TUTT with comm 1.5
FIIT widhulll
A A"MACE goNV with
AMMCTS "o will aguu
175
175
Number of Docaii 1063)
Namber of
Figure 6: Using Value and Policy Networks for search in the Generative Model with polynomially decaying noise and 1 0.5.
Figure 7: Using Value and Policy Networks for search in the Generative Model with exponentially decaying noise and 7) = 0.5.
7 CONCLUSION
We introduce A*MCTS, search algorithm that uses pre-trained value/policy networks to guide exploration and learn to make optimal decisions. We provide expected sample complexity bounds and demonstrate theoretically and experimentally that our algorithms work efficiently for reasonable models of reward distributions and noise (in value/policy network estimates) distribution. Future work includes more rigorous experimental analysis, improved search algorithms that automatically adapts to the noise level of the value/policy networks, and applications real scenarios.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Imad S AlShawi, Lianshan Yan, Wei Pan, and Bin Luo. Lifetime enhancement in wireless sensor networks using fuzzy approach and a-star algorithm. 2012.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. JEEE Transactions on Computational Intelligence and Al in games, 4(1):1 1-),,,44,3100 2012.
Hung-Che Chen and Jyh-Da Wei. Using neural networks for evaluation in heuristic search algorithm. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
Pierre-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search. arXiv preprint cs/0703062, 2007.
Daniel Delling, Peter Sanders, Dominik Schultes, and Dorothea Wagner. Engineering route planning algorithms. In Algorithmics of large and complex networks, pp- 117-139. Springer, 2009.
Ali Ghaffari. An energy efficient routing protocol for wireless sensor networks using a-star algorithm. Journal of applied research and technology, 12(4):815-822 2014.
Evangelos Kanoulas, Yang Du, Tian Xia, and Donghui Zhang. Finding fastest paths on road network with speed patterns. In 22nd International Conference Data Engineering (ICDE"06), pp. 10-10. IEEE, 2006.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning, In European conference on machine learning, pp. 293.293. Springer, 2006.
Renato Negrinho and Geoff Gordon. Deeparchitect: Automatically designing and training deep architectures. arXiv preprint arXiv:1704.08799 2017.
Masoud Nosrati, Ronak Karimi, and Hojat Allah Hasanvand. Investigation of (star)tar) search
algorithms: Characteristics, methods and approaches. World Applied Programming, 2(4):251-256. 2012.
Keyur Rana and Mukesh Zaveri. A-star algorithm for energy efficient routing in wireless sensor network. Trends in Network and Communications, pp. 232-241. Springer, 2011.
Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, (1(3):203-230 2011.
Devon Sigurdson and Vadim Bulitko. Deep learning for real-time heuristic search algorithm selection.
In Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference, 2017.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of without human knowledge. Nature, 550(7676):354, 2017.
Joel Veness, Mare Lanctot, and Michael Bowling. Variance reduction in monte-carlo tree search. In Advances in Neural Information Processing Systems. pp. 1836-1844 2011.
Jingyuan Wang, Ning Wu, Wayne Xin Zhao, Fanzhang Peng, and Xin Lin. Empowering a search algorithms with neural networks for personalized route recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 539-547. ACM, 2019a.
Linnan Wang, Yiyang Zhao, Yuu Jinnai, and Rodrigo Fonseca. Alphax: exploring neural architectures with deep neural networks and monte carlo tree search. arXiv preprint arXiv: 1rX5v:1805.0 1805.074-10 2018.
11

---

Under review as a conference paper at ICLR 2020
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efiiiien neural architecture search by learning action space. arXiv preprint arXiv:1906.06832, 2019b.
Martin Wistuba. Finding competitive network architectures within a day using uct. arXiv preprint 17Xiv:171,.07420, 2017.
12

---

Under review as a conference paper at ICLR 2020
8 APPENDIX
8.1 PROOF OF THEOREM
Proof. Firstly, the event that all states sd satisfy |Xxal = |Vsa Una S ca happens with probability
1- B, where Xa are i.i.d. copies of Xa. This is because that ca chosen that IP Ueaa S
ca) 2 1 DK for each 8y Therefore, taking union bound over Kd states at depth and then over all D levels ensures that the event & happens with probability 1 3.
A MCTTS-V chooses iteratively the state sa with the highest UCB estimate, Us. + Ca and queries the value network for the values of each the K children of sa. Under event &, the UCB estimate Usa + Ca is always an over-estimate of Vas Since the algorithm always take from the queue the state sa with the highest UCB estimate Una + ca and it only stops when the queue Q of possible candidates has only one leaf element, the algorithm is guaranteed to find 1* Suppose otherwise. i.e., [Q] and Q contains a leaf state I where Vi < V*. Then for an intermediate state that is an ancestor 1", < Va,- = V* < Us₁ + ca under the event & Therefore, as Q is sorted in descending order according to the UCB estimates, must be ahead of I in Q, which is contradiction.
To estimate the complexity, one needs to think about how many non-optimal internal nodes are queried using the value network. Notice that sub-optimal internal node 8ą is chosen if V < Una + Cd = Va, + xx, + Cd- Then it is necessary to understand the probability of the event that Ara X., Ca 2 O, because under that event the algorithm does not need to query the value network for su. Therefore the sample complexity (i.c. the number states for which the value network is queried) is the given by
N
E K. 2
Des - ca 50
Dow Xay cæ s
ser EA(se)
where K is the number of children of each node, and A(sa) is the set of ancestors of state 8d-
Since V., -V VV. A., = 0 whenever 8a E A(("). Moreover, because |Xa, I ca under event E, follows that the expected sample complexity is
E[N] KD+
Σ
K.P
Ass
Xxs, Cd S0
N
Aes Xxx Ce 50
se EA(sa)
L
8.2
PROOF OF THEOREM 2
Proof. Firstly, the event & that all states sa satisfy [V., - U.al S and VV,, - U S cj happens with probability 3, following the same union bound argument in Theorem
The correctness of A A'MCTS-x"V' follows largely from the proof of correctness for "MCTS-V". The main difference in the two algorithms in the new sampling condition for r; for > 2, which is that In Pri Pr.-1 2c]+1 To show why this is relevant, let us elaborate the case of 3. Under
the event E, Vr I U + c241, where c241 depends on the noise distribution X Moreover, Vr, 2 U cdt Hence, one should sample r3 if U + 2 U c2+1, i.e. U U < 20
This is because if U., ci+1 < < c2+1 then it impossible for Vr, > Vn,
Since the probabilities are given in softmax form, the condition U.,, - U S 20 equivalent to
1
(
In
Pri
<
2ca+1
Pr.
When combined with the result from Theorem
I it gives the following sample complexity bound:
K-1
Σ
In
Pri
220+1)
Pre
h=2
13

---

Under review as a conference paper at ICLR 2020
Das
Xas
ca c 50
n
Day - Xay - co - cD -0
acrEA(au)
This is equivalent
K
Σ
Σ
Vi1 Vie + +[(411)1 (d+1),1 ((+11)& S 20
S
k=
1
Aos Xea= Cd cD
Aeg -xay Cd' CD 5
Par ELA(sa)
where X (d+1),. is the noise random variable associated with no for the policy network, X (a+1)aa S 205+1) and
iee. U Vra + X (a+1)) The events (Vi, Vr, +
X (d+1),1
Des - Xa1 - cd - 5
N
Day - Xew cB cD - are independent, since Aea
the gap between V and Vea V/, Vra is the difference in value between two children of sa. and these two quantities are uncorrelated.
Therefore our total expected sample complexity is:
K-1
E[N] S
Σ
Σ
P
Vn
Vrr
X(anna X(at1). S 20t111)
SeEL
P
DNs
Xss
Cd 0
n
Day Xay cc $0
By E((o))
8.3 APPROXIMATING 5
Algorithm 3 A A*MCTS-V
Require: Value Network, additive approximation tolerance failure tolerance
1: For each d D, compute ca that IP(IV,, Unal S ca) 2 1 DKa for each 84-
9
2: Calculate D such that cD < 8.
3: Q = (so, Us, + co)
4: while the depth of frfron(() is < δ do
5: (s. Q.pop()
6: for E C(s) do
d depth ofr 8: Q.enqueue( (r, Ur + ca) end for end while
7:
9:
10:
Qroorot(()
12:
Return U, and the action at Sp that leads to
8.3.1 PROOF OF THEOREM 3 FOR ALGORITHM 3
Proof. Under event E, the correctness for Algorithm 3 A LCMTS-- largely follows the proof in
Theorem [
with the exception that the algorithm stops when the most optimistic state in the queue Q special intermediate depth D. Let [" be the state depth D that achieves arg max Usa + ca.
e.EQ
14

---

Under review as a conference paper at ICLR 2020
For every node si depth D, Q contains ancestor of sp. Under the event &, every estimate Usa + Ca is a valid upper bound of Ve, and the true value of s& s descendants. follows that Uz. c - V 2 U/. + c.. Therefore, Up. approximates V up to additive error d when cp 6.
In order to reason about the sample complexity, notice that we query the value network for a state sa if Üp. < U.J + ca < V. + Xxy + Cæ with the additional requirement that < D. Therefore, is sufficient consider the event where Up. Va, S Xx, + Cd. Since Up. lower-bounded by V cB. it suffices to consider the event of V V.a Xxx + + cD-
Therefore the sample complexity N of states queried using the value network is upper-bounded by
N Σ K.1
Ass Xoa -cd c 50
n
Dew New c S =0)
ddES,dcD
02t (A(aa)
Since As, whenever A(1*) and |Xxal S Ca under event &, follows that the expected sample complexity is
BMM] KN+ Σ K.P Aaj Xx Cd c 5O
n
Asy Xsy Ca' - $0
6aE8
Sat E(((sa)
d<D *atA((I))
8.4 CONSTANT GAP MODEL
The first example we will consider is the constant gap model, where A(I = 7 for any + 1", and the noise variables Xd, XI are mean-O Gaussian random variables.
8.4.1 USING VALUE NETWORK
Lemma 1. In the Constant Gap Model, the expected sample complexity for Algorithum 7 is:
D-1d-1
B = KD ΣΣ
(K - II
KIP(1) X(d-s) ((d-)) S 0)
d=1
j=0
This translates to a sample complexity [[N] S KD D² 1)K2 for some constant c. that
satisfies de -ve2 2 Volog K.
Proof. For MCMSS-V Algorithm
Theorem
the sample complexity
E[N] KD+
Σ
K-P A., X., - cc
Deg Xx - 50
(A
4ur EA(sa)
easy to evaluate, because the individual events Des - Xea ca S 0 and Deg - -Xay - Ca S 50 are independent. We claim that
E
K. IP]
Dos -xa - 50 n
Deg - Nag - Cd' 5
# Lu
EA(ea)
equivalent
D l d-1
(K - 1) II KP(n - X(a-s) -(--) S 50)
1=0
j=0
To see why this the case, we can reason about the first few levels. At depth d = 1, we choose to expand state with probability P(n
X1 ei 0). There are K states where 81 A(l*).
15

---

Under review as a conference paper at ICLR 2020
If expand particular node, the sample complexity is K. Therefore the expression would be (K - (-)))() P(1 - X1 - c1 - 0).
At depth d = 2. there are (K (K) states whose depth ancestor is not in A(l"). For these states, we choose to expand each with probability P(1 - X2 22 S () - X1 - C1 S 0). The sample complexity for each expansion is K, so in expectation,
X2 c S (1) X Cj I 0) states. There are also K states who are not A(?*) but their parent in depth 1 A(l)), and we expand them with probability P( X2 c2 I 0). For these states, query (K 1)(K)P(()) - X2 C2 < 0) states in expectation. Continuing this reasoning through for depths 3.... yields the final expression Equation
query (K ()
Therefore the expected sample complexity is:
D-1d-1
E E = KD
(K - 1) II KIP(1) X(d-5) -(d-)) 50)
5=0
We rewrite the above
D-1d-1
E KD ΣΣ
(K- 1) II
(P(( 21 2n
d=1
j=0
which is equivalent to:
D-1d-1
B[N] = KD+
ΣΣ (K-1)
KPP
72 1 1- - (id (d- 1)
(dds))
d=1
j=0
where Z is the standard normal distribution.
Standard tail inequalities gives us that P(Z 2) ( 22 holds for >
c Se where the last inequality
We are interested a value for / such that e < e log K
This is achieved when = v2 log K. For exponentially decaying standard deviation function of depth, i.e., do for >> when
?) (d-))) vd-j f. a(e-;; / (d (d- S K
Since and K are constants, there exists constant such that
7 (d-1) V(d - 2 22 K
whenever j c.
Therefore, the sample complexity is bounded by: [[N] < KD + D2 -
33)
which is polynomial in the depth D.
For polynomially decaying standard deviation function of depth, i.e., dd 7 (d j) /d - t
for > 1, when
a(-))) (dd 5) S k
Since a, and K are constants, there exists constant c' such that
7) (d - j)a ( (d j) 2 /2 log K whenever j 2 c', and a similar sample complexity to Equation holds.
8.4.2 6-APPROXIMATE VALUE ESTIMATION
The above reasoning generalizes naturally to a 6-approximate value estimation using A MCCTS-. Algorithm 3 and the expected sample complexity is:
D-1d-1
E[N] = KD +
ΣΣ
(K - 1) II
KP(n X(d-5) 1) 9(d-)) cD 0)
1=1 1
3=0
16

---

Under review as a conference paper at ICLR 2020
8.4.3 USING VALUE AND POLICY NETWORK
Lemma 2. In the Constant Gap Model, the expected sample complexity for Algorithm 2 is:
D-1
K
B[N]
Σ
2+
Σ
P ( ((412), + X(a+1), S $20(11)
d=o
2
D-ld-1
K-1
2+
II KP Xa-j - Cd-j 50) P + X(a + ((a-1),2 S 202_1) Σ
d=
2=
Proof. The policy network for this constant gap problem model is not extremely useful, because for suboptimal states, the immediate children have the same optimality gap. and therefore, the probabilities given by the policy network will be fairly evenly distributed among the immediate children nodes. The policy network give more differentiated probabilities for the immediate children of a parent state that is an ancestor of the optimal leaf.
First, the sample complexity KD for the optimal path can be improved to
D-1
Σ
2
Σ P ( + X(411z S $20211)
2=0
For the ancestor leaf at level d, the number of child leaves that we would expand in expectation using the information from the policy network is 2
K-1
Σ P (1 ((+1)), + (( S 202+1)
2=
The second expression can be improved to:
D-1d-1
K-1
ΣΣ
2 P X(a- + ((a-1),2 2c)_,)
II [PP(n-Xa-a Xa-; Cd-j $0).
To see why this is the case, reason about the first few levels. At depth d = 1, choose to expand state with probability IP(1) - X1 C1 S S).. There are K states 81 where 81 & A(("),
K-1
but in expectation we only consider 2 + Σ k=
P ( X + X S 2cT) of these states based on
the information from the policy network. If we expand a particular state, the sample complexity is K, since all K children nodes have the same value in this constant gap model, the sampling criteria using probabilities from the policy network will always met. Therefore the expression would be
2
P (1) + ( + X(1,2 S 207)
(K) P(n X1 - 6 S).
K 2 Σ k=2
At depth d = 2, there are in expectation
(K) states that we would consider expanding from whose depth ancestor is not in A( For these states, we choose to expand each with probability P(1 - X2 - 02 S 0)P(n X1
P + X(1)1 X(1)22 S 2c7)
< 0). The sample complexity for each expansion is K, so in expectation, we query
K-1
2+
Σ P( X(),1 X S 2cT) (K²)P() X2 c2 S 0)P(1 X1 ci 0) states.
2
There are also K - 1 states who are not in A(I*) but their parent in depth 1 are in A(I), and states, expectation,
we expand them with probability P(n - X2 - 02 I 0). For these
P (1 X(2).1 + +X12),2 I 207) of them, therefore, we expect K Σ
we have expanded only
+
K- Σ P
to query
2 +
Xay,1 + X S 22c7) (K)P(1- X₂ C2 S 0) states in expectation. (n +
2=2
Continuing this reasoning through for depths 3.... D - 1 yields the final expression:
D-1
K-1
E[N =
Σ
2
Σ
(n + X(a41),1 + X(441) S 2cH+1)
d=0
2=2
17

---

Under review as a conference paper at ICLR 2020
d-Id-1 R-1
2+
Σ
p
((a-)ja + X(a-i), s 262_))
II
KIP((- Xa-s Cd-j 50)
d=
2=2
==
For 6-approximate value estimate, similar arguments apply give sample complexity of:
d'-1
K
E[N]-
Σ
2+
Σ
P (n + ((+1)),1 + X(at1)a $26711)
d=0
h=2
K-1 + Σ
i
PP
(n
X (d-)11 + (a- S 20%_i)
KP(1) Xa-s -dds S S0). II i=0
k=2
8.5 GENERATIVE MODEL
The model generates the value function of the nodes in the Markov decision tree in a recursive way. This model first chooses the optimal value Ve, V* at the root so- Given the value function of parent node p. the value functions for the children rı, ; are generated as follows: one of the children (without loss of generality, say r1) has the same value function as the parent Vp; each of the remaining children r; has a value function V,, - Y with Y sampled independently from ~ U[O, n/) the uniform distribution over the interval [0, v). At level d, there are exactly (K) - 1) states with value function distributed according to V (Yi + Yt). When is non-negligible, Yi +...+++ Yt concentrates constant value tn/2 by the concentration of measure phenomenon.
Using value networks. Let us consider the expected complexity of Algorithm for this model. In the algorithms, Ca do for some constant C. Following the estimate in Theorem the overall complexity can be bounded up to an extra KD term by
ΣΣ (O)K-1jp Xa ==
n - ca -
d ΣΣ d=1
(9
1)'P 2>
n -vva 2
2
where Z is a standard normal distribution. The goal to bound this by quantity polynomial (rather than exponential) in D when 1), K, and a are considered fixed. To proceed, we introduce T(d)= 2(v2log k+1)
For any t 2 T(d).
1 7
εva) Se log Kd = K-d
20
Therefore, for a fixed d.
Σ (K)--1jpP))
nt
-vv
öVd < Σ (UU--I' Σ (()K--18
2
20a
T(d))
(=)(d)
t=0
Therefore, up to term linear in D, the sample complexity can be bounded by
T(d)
ΣΣ (K- (K- 1)'P 7 nl
ova)
(4)
20
d=1
Notice first that P(Z >
nt
-Vd) is always bounded by 1. Second, since in both the exponential
and polynomial noise models aa decays faster than 1/ 1/vd asymptotically, T(d) 2(V2log K /+1iydda is uniformly bounded by a constant C(K, 77, a) due to the exponential decay in d. Therefore, the term which is polynomial (rather than exponential) in the depth D.
(4) can be bounded by
Using value and policy networks. Let consider Following the argument of the constant gap model, it can be bounded by
the expected complexity of Algorithm 2
Σ
D T(d)
4 (K - 1) 2
K-1
Σ
P(n
X + X S 2c,²)
P
2
qtt
ova).
205
d=l
2
18

---

Under review as a conference paper at ICLR 2020
which is also polynomial in D it improves over the complexity of using just the value network. Approximating V* using value and policy networks. For a d-approximate value estimate using value network, one can stop early at level D instead and the complexity analysis gives a bound
D T(d) ΣΣ ΣΣ (=K 1)'2 2 20.
=
qt -vva
For a 6-approximate value estimate using both policy and value networks, one can stop early at level D instead and the complexity analysis gives a bound
K-1 Σ
Σ
(K-
2
P P
X
+ +X22 S 207))
P z nt
ōva)
20d
d=1
19


Reviews:
[{"review_id": "SkeXSQ86tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a novel search algorithm that uses the policy and value predictors to guide search and provides theoretical guarantee on the sample complexity. The aim is to estimate the optimal value of an initial state as well as the one-step optimal action to take.\nThe algorithm uses a priority queue to store all states being visited so far and picks the most optimistic one to expand, according to an upper confidence bound heuristic function. The algorithm assumes access to pre-trained value and policy networks and it uses calls to these networks to prioritize the next state to be explored.\n\nThe authors consider a very restrictive setting: \n- Finite horizon Markov decision tree:  no backtrack \n- No intermediate reward and only reward at the end of the episode.\n- Deterministic transition\n- Importantly, access to value network that gives noisy estimates of the optimal value function \n- The noise model is additive and i.i.d and satisfies a concentration inequality\n\nAll this assumption makes the setting very simple and unrealistic. Moreover, I think we can frame the problem into bandit problem and solve it easily with sample complexity independent of the horizon D.\nIn fact, given an initial state s, we consider the K possible actions  a_1, a_2, …, a_K that lead deterministically to next states (r_1, r_2, …, r_K). As the intermediate reward is zero, the state-action value of (s, a_k) is equal to V_{r_k}. As we have noisy estimates of V_{r_k} and we know precisely the noise model, we can run UCB-like algorithm for multi-armed bandit where each arm corresponds to action a_k and expected reward correspond to V_{r_k}. This determines the optimal action in constant time with respect to the horizon.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lF9obI9r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes A*MCTS, which combines A* and MCTS with policy and value networks to prioritize the next state to be explored. It further establishes the sample complexity to determine optimal actions. Experimental results validate the theoretical analysis and demonstrate the effectiveness of A*MCTS over benchmark MCTS algorithms with value and policy networks.\n\nPros:\nThis paper presents the first study of tree search for optimal actions in the presence of pretrained value and policy networks. And it combines A* search with MCTS to improve the performance over the traditional MCTS approaches based on UCT or PUCT tree policies. Experimental results show that the proposed algorithm outperform the MCTS algorithms.\n\nCons:\nHowever, there are several issues that should be addressed including the presentation of the paper:\n•\tThe algorithm seeks to combine A* search with MCTS (combined with policy and value networks), and is shown to outperform the baseline MCTS method. However, it does not clearly explain the key insights of why it could perform better. For example, what kind of additional benefit will it bring when integrating the priority queue into the MCTS algorithms? How could it improve over the traditional tree policy (e.g., UCT) for the selection step in MCTS? These discussions are critical to understand the merit of the proposed algorithms. In addition, more experimental analysis should also be presented to support why such a combination is the key contribution to the performance gain.\n•\tMany design choices for the algorithms are not clearly explained. For example, in line 8 of Algorithm 2, why only the top 3 child nodes are added to the queue?\n•\tThe complexity bound in Theorem 1 is hard to understand. It does not give the explicit relations of the sample complexity with respect to different quantities in the algorithms. In particular, the probability in the second term of Theorem 1 is hard to parse. The authors need to give more discussion and explanation about it. This is also the case for Theorems 2-4. The authors give some concrete examples in Section 6.2 for these bounds. However, it would be better to have some discussion earlier right after these theorems are presented.\n•\tThe experimental results are carried out under the very simplified settings for both the proposed algorithm and the baseline MCTS. In fact, it is performed under the exact assumption where the theoretical analysis is done for the A*MCTS. This may bring some advantage for the proposed algorithm. It is not clear whether such assumptions hold for practical problems. More convincing experimental comparison should be done under real environment such as Atari games (by using the simulator as the environment model as shown in [Guo et al 2014] “Deep learning for real-time atari game play using offline monte-carlo tree search planning”).\n \nOther comments:\n•\tIt is assumed that the noise of value and policy network is zero at the leaf node. In practice, this is not true because even at the leaf node the value could still be estimated by an inaccurate value network (e.g., AlphaGo or AlphaZero). How would this affect the results?\n•\tIn fact, the proof of the theorems could be moved to appendices.\n•\tIn the first paragraph of Section 6.2, there is a typo: V*=V_{l*}=\\eta should be V*-V_{l*}=\\eta ?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkefd1gj9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents the search algorithm A*MCTS to find the optimal policies for problems in Reinforcement Learning. In particular, A*MCTS combines the A* and MCTS algorithms to use the pre-trained value networks for facilitating the exploration and making optimal decisions. A*MCTS refers the value network as a black box and builds a statistical model for the prediction accuracies, which provides theoretical guarantees for the sample complexity. The experiments verify the effectiveness of the proposed A*MCTS. \n\nIn summary, I think the proposed A*MCTS algorithm is promising to push the frontier of studies of the tree search for optimal actions in RL. But the experiments should be improved to illustrate the reasons for the hyper-param setting. For example, in Sec. 6.2, the authors should give some explanations on why the depth of the tree is set as 10 and the number of children per state is set as 5. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed an extension of the Monte Carlos Tree Search to find the optimal policy. The method combines A* and MCTS algorithms to prioritize the state to be explored. Compare with traditional MCTS based on UCT, A* MCTS seem to perform better.

One concern of the reviewers is the paper's presentation, which is hard to follow. The second concern is the strong restriction of assumption, which make the setting too simple and unrealistic. The rebuttal did not fully address these problems.

This paper needs further polish to meet the standard of ICLR.

Decision: Reject