Year: 2019

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 AMCTS, 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.

heading: 1 INTRODUCTION
text: Monte Carlo Tree Search (MCTS) is an online heuristic search algorithm commonly used to find optimal policies for problems in reinforcement learning. It is a vital component of recent breakthroughs for AI in game play, including AlphaGo and AlphaZero (Silver et al., 2016; 2017).
An interesting difference between the MCTS used in AlphaGo/AlphaZero and traditional MCTS is 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; Negrinho & Gordon, 2017; Wang et al., 2019b).
Despite the empirical success and recent popularity, theoretical foundations are lacking. (Kocsis & Szepesvári, 2006; Coquelin & Munos, 2007) analyze MCTS with rollouts using a 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?MCTS, which is a combination of A? (Delling et al., 2009; Kanoulas et al., 2006) and MCTS. Like A?, it uses a 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 a statistical model is built the accuracy of the predictions. In particular, we assume the standard deviation of the noisy estimates of intermediate state values decays (either polynomially or exponentially) as a function of the depth of the tree, so that the values of near-terminal states are estimated to a greater degree of accuracy. With this statistical model, we provide theoretical guarantees for the sample
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 A?MCTS 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.

heading: 2 BACKGROUND AND RELATED WORK
text: 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 in 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 is commonly used to search for a one-step optimal actions from the root. The agent then takes this action, observes the result, transitions to a new state, and repeats MCTS starting from this 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 in the tree that should be expanded. On the theoretical side, there is a small body of literature that addresses the theoretical foundations of MCTS with random rollouts (Kocsis & Szepesvári (2006), Veness et al. (2011)). The algorithm, called UCT (UCB applied to trees) models the search as a complex multi-armed bandit problem where the rewards are allowed to drift over time. The analysis shows that after a period of time T , only the optimal branch will be followed. Veness 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 a weighted combination of the value network’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; 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, to the best of our knowledge, we are not aware of any prior work that performs theoretical analysis of such heuristic based A? algorithms.

heading: 3 PRELIMINARIES AND SUMMARY OF CONTRIBUTIONS
text: 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 s0 and the process terminates at horizon D with a termination reward that depends on the end state. We assume that there are 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 at depth d as sd and also a leaf state as l ∈ L. There is a 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 ∈ L, then Vs is the termination reward of that particular leaf. For an intermediate node s, Vs = maxl∈L(s) Vl, where
L(s) is the set of leaf nodes that share s as an ancestor, i.e., the set of leaf nodes in the subtree rooted at s. We assume that the highest value V ∗ ≡ maxl∈L Vl = maxs∈S Vs is achieved at a unique leaf node l∗ = arg maxl∈L Vl.
In this work, we focus on the problem of efficiently computing V ∗ exactly or approximately with a controlled accuracy without direct access to the value function V : S → R, as a stepping stone to finding the optimal one-step action from s0. Instead, there is a 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 sd at depth d, Usd ≡ Vsd +Xsd , where Xsd are i.i.d. copies of a random variable Xd that depends only on the depth d. We assume that at depth D, which is the level with all the leaf nodes, Ul = Vl (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 a state. In the worst case, all leaves need to be queried and the sample complexity is KD.
Another type of available pre-trained black box resource is a policy network. Let C(s) = {r1, . . . rK} denote the set of K children of state s, each corresponding to the transition state of one of the K actions {a1, . . . aK}. The policy network outputs a probability estimate of the form pri = e Uπri∑K
k=1 e Uπrk
,
where each Uπri is a perturbed estimate of Vri . Here the superscript π indicates that this is the approximation from the policy network. We assume that if the child ri is at depth d then the estimate Uπri = Vri + X π ri , where X π ri are i.i.d. copies of a random variable X π d that depends only on the depth d. We assume that the distribution of Xd and Xπd are known a priori for each depth d. Further, the variances of Xd and Xπd decrease sufficiently rapidly as the depth d increases (i.e., as one traverses deeper in the tree, the noise level is smaller). This assumption is motivated by basic approximate dynamic programming principles, which is that near-terminal states require a 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.

heading: 3.1 MAIN CONTRIBUTIONS
text: 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 on our optimistic estimates Usd + cd 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:
• Section 4 introduces and analyzes A?MCTS-V ∗ and A?MCTS-π∗V ∗ that are our core techniques for estimating V ∗ exactly. A?MCTS-V ∗ uses only a value network to determine V ∗ exactly and outputs the optimal one-step from s0 that leads to l∗. We give an expected sample complexity in Theorem 1. A?MCTS-π∗V ∗ builds onA?MCTS-V ∗ by using a policy network to further reduce the sample complexity, which we bound in Theorem 2. • Section 5 extendsA?MCTS-V ∗ andA?MCTS-π∗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.

heading: 4 FINDING V ∗ EXACTLY USING VALUE AND POLICY NETWORKS
text: This section presents our main techniques, A?MCTS-V ∗ and A?MCTS-π∗V ∗, which find V ∗ exactly using a value network only in the former and a value network and a policy network in the latter.
A?MCTS-V ∗, Algorithm 1, uses only a value network to determine V ∗ exactly and outputs the optimal one-step action from s0 that takes the agent to an 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 s0, compute their value network estimate plus the exploration bonus, and then insert these nodes to a priority queue Q. The exploration bonus, denoted by cd, is chosen such that P(|Vsd − Usd | ≤ cd) ≥ 1 − β DKd
. 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 is a leaf node. Since the value network gives the values of leaf nodes exactly, this leaf node must be l∗.
We present the complexity bound in Theorem 1. The complexity bound is based on 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 a sub-optimal internal node sd is chosen if V ∗ ≤ Usd + cd = Vsd +Xsd + cd, where Usd is the value network estimate for state sd, and cd is the upper bound on the possible error for the value estimate. We should also account for the ancestors of sd, if we are lucky enough to be able to rule out one of the ancestors of sd, we would never expand beyond that ancestor to reach sd, and sd would not be in our priority queue. Theorem 1 states this complexity bound. Theorem 1. With probability 1− β, Algorithm 1, A?MCTS-V ∗, returns V ∗. The expected sample complexity (number of calls to the value network) is E[N ] = KD+ ∑
sd∈S,sd /∈L,sd /∈A(l∗)
K·P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  ,
Algorithm 1 A?MCTS-V ∗
Require: Value Network with error distribution for Xd at each depth d ≤ D 1: For each d < D, compute cd so that P(|Xd)| ≤ cd) ≥ 1− βDKd . 2: Q← (s0, Us0 + cd) 3: while the depth of Q.front() is < D do 4: (s, ) = Q.pop() 5: for r ∈ C(s) do 6: d← depth of r 7: Q.enqueue(r, Ur + cd) 8: end for 9: end while 10: (s, )← Q.front() 11: Return Us and the action at s0 that leads to s
where A(l∗) is the set of ancestor states of the optimal leaf, l∗, and ∆sd = V ∗ − Vsd .
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 ∆sd and the errors Xsd ). We give two examples in 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.

heading: 4.1 COMBINING VALUE NETWORK WITH POLICY NETWORK
text: Suppose that in addition to the value network U , one has access to a policy network Uπ that outputs, for each child of s, r1, . . . rK (each corresponding to the transition state of a different action a1, . . . aK) a probability estimate of the form:
pri = eU π ri∑K
k=1 e Uπrk
,
where each Uπri = Vri + X π ri is a perturbed estimate of Vri . If ri is at depth d, the noise X π ri is an i.i.d. copy of the random variable Xπd that depends only on the depth d. Since all the probabilities are known, we assume without loss of generality that states r1, . . . rK are ordered so that Uπr1 ≥ U π r2 ≥ U π r3 . . . ≥ U π rK , or equivalently pr1 ≥ pr2 ≥ pr3 . . . ≥ prK . The following algorithm A?MCTS-π∗V ∗ uses both the value and the policy networks to determine V ∗ exactly. When we expand a given state sd, instead of querying for the value estimate for every child of sd and adding each child to 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 k > 2, we add this child if there is 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 is given by the noise model. Intuitively, we are saying that if this gap is 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, so we do not have to add it to the queue.
The key insight behind this algorithm is that, if there is a large gap between the probabilities of the children as given by the policy network, one can infer that the children states associated with the smaller probabilities are not worth expanding because they have small values. This is made rigorous in the statement and proof of Theorem 2. Theorem 2. With probability 1− β, Algorithm 2, A?MCTS-π∗V ∗, returns V ∗. The expected sample complexity (number of calls to the value network) is
E[N ] ≤ ∑ sd /∈L
( 2 +
K−1∑ k=2 P ( Vr1 − Vrk +Xπ(d+1),1 −X π (d+1),k ≤ 2c π d+1 )) ·
P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  ,
Algorithm 2 A?MCTS-π∗V ∗
Require: Value Network, Policy Network, failure tolerance β 1: For each d < D, compute cd so that P(|Xd| ≤ cd) ≥ 1− β2DKd . 2: For each d < D, compute cπd so that P(|Xπd | ≤ cπd ) ≥ 1− β 2DKd
. 3: Q← (s0, Us0) 4: while the depth of Q.front() is < D do 5: (s, ) = Q.pop() 6: for i ∈ [1, . . . ,K], ordered according to the probabilities of the policy network do 7: d← depth of ri 8: if i < 3 or ln ( pr1 pri−1 ) ≤ 2cπd then
9: Q.enqueue(ri, Uri + cd) 10: else 11: break; 12: end if 13: end for 14: end while 15: (s, )← Q.front() 16: Return Us and the action at s0 that leads to s
where ∆sd = V ∗ − Vsd , and Xπ(d+1),k is the random variable associated with rk for the policy network, i.e., Uπrk = Vrk +X π (d+1),k.
As with Theorem 1, getting an exact expression for the expected sample complexity depends on the problem model (the distribution for the gaps ∆sd and the errors Xsd). We give two examples in 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.

heading: 5 APPROXIMATING V ∗ USING VALUE AND POLICY NETWORKS
text: This section extends the algorithms to the problem setting where we are willing to tolerate an additive error δ in the estimate for V ∗
We first consider the extension of A?MCTS-V ∗, Algorithm 1. The key idea is that it suffices to stop searching at a depth D̃ whenever cD̃ ≤ δ. As long as the most optimistic state at depth D̃ is identified, the value of this state approximates V ∗ up to an additive error δ. The main result is stated in Theorem 3 and the algorithm is Algorithm A?MCTS-V̂ , presented in Appendix 8.3.
Theorem 3. With probability 1 − β, Algorithm 3, A?MCTS-V̂ , returns V ∗ up to additive error δ. The expected sample complexity (number of calls to the value network) is
E[N ] ≤ KD̃+ ∑ sd∈S d<D̃
sd /∈A(l∗)
K·P ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0 
where A(l∗) is the set of ancestor states of the optimal leaf, l∗, and ∆sd = V ∗ − Vsd , and D̃ is the minimum depth at which cD̃ ≤ δ
Using the same reasoning as the one forA?MCTS-V̂ , we can extendA?MCTS-π∗V ∗ to the following result.
Theorem 4. With probability 1 − β, one can find V ∗ up to additive approximation error δ using expected sample complexity (number of calls to the value network):
E[N ] ≤ ∑
sd,d<D̃
( 2 +
K−1∑ k=2 P ( Vr1 − Vrk +Xπ(d+1),1 −X π (d+1),k ≤ 2c π d+1 )) ·
P ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0  , where D̃ is the minimum depth at which cD̃ ≥ δ.

heading: 6 MODELS AND EXPERIMENTS
text: In this section, we discuss two simple yet representative models for the Markov decision tree and show that the sample complexity is polynomially bounded under reasonable noise models.
6.1 CHOOSING cd FOR GAUSSIAN NOISE
The noisesXd,Xπd are taken to be GaussianN (0, σ2d) random variables. Two noise models are tested. The first is a Gaussian with an exponentially decaying standard deviation, i.e., Xd, Xπd ∼ N (0, 1α2d ) for some α > 1. The second is a Gaussian with a polynomially decaying standard deviation, i.e., Xd, X π d ∼ N (0, 1d2γ ), for some γ > 1. The experiments are carried out for α = 1.3 and 1.5 for the exponential case and γ = 1.3 and 1.5 for the polynomial case.
The assumption of decaying standard deviation as a function of depth is motivated by basic approximate dynamic programming principles, which we elaborate on in Section 3.
The choice of cd is essential to the performance of the algorithms. Standard concentration inequalities for sub-Gaussian random variables state that P(|Xd| ≥ cd) ≤ 2e −c2d 2σ2 d , and this probability expression is required to be less than β DKd . After substituting it in, we arrive at cd = O( √ dσd).

heading: 6.2 CONSTANT GAP MODEL
text: In the constant gap model, V ∗ − Vl∗ = η for a fixed constant η > 0 and Vl = 0 for any other leaf l 6= l∗. Therefore, the gap ∆(l) = η for any l 6= l∗. The noise variables Xd, Xπd are mean-zero Gaussian random variables.
Using value network. The expected sample complexity for Algorithm 1 is
E[N ] = KD + D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(η −X(d−j) − c(d−j) ≤ 0)  .
This translates to a sample complexity of E[N ] ≤ KD +D2(K − 1)Kc, for the smallest constant c that satisfies ησc − √ c ≥ √ 2 logK.
The analysis for this result, as well as similar analyses and sample complexity results for Algorithm 2 and the approximate counterparts are in Appendix 8.4.
Experiments. We compare the performance of A?MCTS-V ∗ with the MCTS algorithm that uses the UCB estimate Qs,a + 2c
√ log( ∑ bNs,b)
Ns,a and queries the value network Us instead of expanding state
s with random rollouts, where c is a constant, and Ns,b are visitation counts for choosing action a from state s. We also compare A?MCTS-π∗V ∗ with the PUCT algorithm described in Silver et al. (2017) that uses the UCB estimate Qs,a + c · ps,a · √∑
bNs,b Ns,a
, where ps,a is the probability given by the policy network Uπ .
The experiments are performed on a tree of depth D = 10 with K = 5 children per state. As defined in the constant gap model, the optimal leaf has reward η and all other leaves have reward 0, and we experiment with η = 1 and η = 0.5. In our experiments, we use c = 1 in the the bonus UCB expression for benchmark MCTS and PUCT algorithms. Our algorithms set cd = 5 · √ dσd, where σd is the variance of the Gaussian noise. This choice is justified earlier in Section 6.1.
Since the main use case for these algorithms is to find the optimal one-step action from s0, we collect data on the one-step action that the algorithm would output at every 1, 000 expansions (or queries to the value network U ). MCTS algorithms would output the one-step action from s0 with the highest visitation count. Our algorithms would output the action from s0 that leads to s, where s is the highest-valued element in the current priority queue Q based on the value network estimate Us. We give an overall budget of 20,000 expansions and note whether or not (so the data is 1 or 0) the algorithm chooses the right one-step action. Each of our experiments average over 200 trials. Tables 1 and 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 and 4 show the success proportion over time, at successive 1000 expansion intervals for Algorithm 2 and PUCT for η = 0.5 in both noise models (polynomially and exponentially decaying).

heading: 6.3 GENERATIVE MODEL
text: 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 Vs0 = V
∗ at the root s0. Given the value function of a parent node p, the value functions for the children r1, . . . , rK 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 ri has a value function Vp − Y with Y sampled independently from ∼ U [0, η], the uniform distribution over the interval [0, η]. At level d, there are exactly ( d t ) (K − 1)t states with value function distributed according to V ∗− (Y1 + . . .+Yt). When t is non-negligible, Y1 + . . .+Yt concentrates at constant value tη/2 by the concentration of measure phenomenon.
Figure 3: Using Value and Policy Networks for search in the Constant Gap Model with polynomially decaying noise and η = 0.5.
Using value networks. Following the estimate in Theorem 1, the overall complexity for Algorithm 1 can be bounded up to an extra KD term by
D∑ d=1 d∑ t=0 ( d t ) (K − 1)tP ( Xd ≥ ηt 2 − cd ) = D∑ d=1 d∑ t=0 ( d t ) (K − 1)tP ( Z ≥ ηt 2σd − C̃ √ d ) where Z is a standard normal distribution. The goal is to bound this by a quantity polynomial (rather than exponential) in D when η, K, and α are considered fixed. To proceed, we introduce T (d) = 2( √ 2 logK+1) √ dσd
η . For any t ≥ T (d), P ( Z ≥ ηt
2σd − C̃ √ d
) . e− logKd = K−d.
Therefore, for a fixed d, d∑
t=T (d)
( d
t
) (K−1)tP ( Z ≥ ηt
2σd − C̃ √ d
) ≤ d∑ t=T (d) ( d t ) (K−1)tK−d ≤ d∑ t=0 ( d t ) (K−1)tK−d = 1.
Therefore, up to a term linear in D, the sample complexity can be bounded by D∑ d=1 T (d)∑ t=1 ( d t ) (K − 1)tP ( Z ≥ ηt 2σd − C̃ √ d ) . (1) Notice first that P(Z ≥ ηt2σd − √ d) is always bounded by 1. Second, since in both the exponential and polynomial noise models σd decays faster than 1/ √ d asymptotically, T (d) = 2( √ 2 logK+1) √ dσd
η
is uniformly bounded by a constant C(K, η, α) due to the exponential decay in d. Therefore, the term (4) can be bounded by (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 2 and the approximate counterparts. We defer this treatment to Appendix 8.5.
Experiments. Our experimental results for the Generative Model follow the same setup and parameters as the experiments for the Constant Gap Model in Section 6.2. Tables 3 and 4 give the proportion of trials that return the correct optimal one-step action at the 20,000-th expansion. Figures 6 and 7 show the success proportion over time, at successive 1000 expansion intervals for Algorithm 2 and PUCT for η = 1 in both noise models (polynomially and exponentially decaying).

heading: 7 CONCLUSION
text: We introduce A?MCTS, a 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 to real scenarios.

heading: 8 APPENDIX

heading: 8.1 PROOF OF THEOREM 1
text: Proof. Firstly, the event E that all states sd satisfy |Xsd | = |Vsd−Usd | ≤ cd happens with probability 1− β, where Xsd are i.i.d. copies of Xd. This is because that cd is chosen so that P(|Vsd − Usd | ≤ cd) ≥ 1− βDKd for each sd. Therefore, taking union bound over K
d states at depth d and then over all D levels ensures that the event E happens with probability 1− β. A?MCTS-V ∗ chooses iteratively the state sd with the highest UCB estimate, Usd + cd and queries the value network for the values of each of the K children of sd. Under event E , the UCB estimate Usd + cd is always an over-estimate of Vsd . Since the algorithm always take from the queue the state sd with the highest UCB estimate Usd + cd and it only stops when the queue Q of possible candidates has only one leaf element, the algorithm is guaranteed to find l∗. Suppose otherwise, i.e., |Q| = 1 and Q contains a leaf state l where Vl < V ∗. Then for an intermediate state sd that is an ancestor to l∗, Vl < Vsd = V
∗ ≤ Usd + cd under the event E . Therefore, as Q is sorted in descending order according to the UCB estimates, sd must be ahead of l in Q, which is a contradiction.
To estimate the complexity, one needs to think about how many non-optimal internal nodes are queried using the value network. Notice that a sub-optimal internal node sd is chosen if V ∗ ≤ Usd + cd = Vsd + Xsd + cd. Then it is necessary to understand the probability of the event that ∆sd−Xsd− cd ≥ 0, because under that event the algorithm does not need to query the value network for sd. Therefore the sample complexity N (i,e. the number of states for which the value network is queried) is the given by
N = ∑
sd∈S,sd /∈L
K · 1 ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  , where K is the number of children of each node, and A(sd) is the set of ancestors of state sd. Since Vsd = V
∗, ∆sd = 0 whenever sd ∈ A(l∗). Moreover, because |Xsd | ≤ cd under event E , it follows that the expected sample complexity is E[N ] = KD+ ∑
sd∈S,sd /∈L,sd /∈A(l∗)
K ·P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0 

heading: 8.2 PROOF OF THEOREM 2
text: Proof. Firstly, the event E that all states sd satisfy |Vsd − Usd | ≤ cd and |Vsd − Uπsd | ≤ c π d happens with probability 1− β, following the same union bound argument as in Theorem 1. The correctness of A?MCTS-π∗V ∗ follows largely from the proof of correctness for A?MCTS-V ∗. The main difference in the two algorithms is in the new sampling condition for ri for i > 2, which is that ln ( pr1 pri−1 ) ≤ 2cπd+1. To show why this is relevant, let us elaborate on the case of i = 3. Under the event E , Vr3 ≤ Uπr3 + c π d+1, where c π d+1 depends on the noise distribution X π d+1. Moreover, Vr1 ≥ Uπr1−c π d+1. Hence, one should sample r3 if U π r2 +c π d+1 ≥ Uπr1−c π d+1, i.e. U π r1−U π r2 ≤ 2c π d+1. This is because if Uπr2 + c π d+1 < U π r1 − c π d+1 then it is impossible for Vr3 > Vr1 .
Since the probabilities are given in a softmax form, the condition Uπr1 −U π r2 ≤ 2c π d+1 is equivalent to
1 ( ln ( pr1 pr2 ) ≤ 2cd+1 ) .
When combined with the result from Theorem 1, it gives the following sample complexity bound:
∑ sd /∈L
( 2 +
K−1∑ k=2 1 ( ln ( pr1 prk ) ≤ 2cπd+1 ))
·1 ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0  . This is equivalent to:
∑ sd /∈L
( 2 +
K−1∑ k=2 1 ( Vr1 − Vrk +Xπ(d+1),1 −X π (d+1),k ≤ 2c π d+1 )) ·
1 ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0  , where Xπ(d+1),k is the noise random variable associated with rk for the policy network,
i.e., Uπrk = Vrk + X π (d+1),k. The events 1 ( Vr1 − Vrk +Xπ(d+1),1 −X π (d+1),k ≤ 2c π d+1 ) and
1 ( ∆sd −Xsd − cd − cD̃ ≤ 0
⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0
) are independent, since ∆sd
is the gap between V ∗ and Vsd , Vr1 − Vrk is the difference in value between two children of sd, and these two quantities are uncorrelated.
Therefore our total expected sample complexity is:
E[N ] ≤ ∑ sd /∈L
( 2 +
K−1∑ k=2 P ( Vr1 − Vrk +Xπ(d+1),1 −X π (d+1),k ≤ 2c π d+1 )) ·
P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  ,

heading: 8.3 APPROXIMATING V ∗
text: Algorithm 3 A?MCTS-V̂ Require: Value Network, additive approximation tolerance δ, failure tolerance β
1: For each d < D, compute cd so that P(|Vsd − Usd | ≤ cd) ≥ 1− β DKd for each sd. 2: Calculate D̃ such that cD̃ ≤ δ. 3: Q← (s0, Us0 + c0) 4: while the depth of Q.front() is < D̃ do 5: (s, ) = Q.pop() 6: for r ∈ C(s) do 7: d← depth of r 8: Q.enqueue(r, Ur + cd) 9: end for
10: end while 11: (s, )← Q.front() 12: Return Us and the action at s0 that leads to s

heading: 8.3.1 PROOF OF THEOREM 3 FOR ALGORITHM 3
text: Proof. Under event E , the correctness for Algorithm 3, A?MCTS-V̂ largely follows the proof in Theorem 1, with the exception that the algorithm stops when the most optimistic state in the queue Q is at a special intermediate depth D̃. Let l̃∗ be the state at depth D̃ that achieves arg max
sd∈Q Usd + cd.
For every node sD̃ at depth D̃, Q contains an ancestor of sD̃. Under the event E , every estimate Usd + cd is a valid upper bound of Vsd and the true value of sd’s descendants. It follows that Ul̃∗ − cD̃ ≤ V ∗ ≤ Ul̃∗ + cD̃. Therefore, Ul̃∗ approximates V ∗ up to additive error δ when cD̃ ≤ δ.
In order to reason about the sample complexity, notice that we query the value network U for a state sd if Ul̃∗ < Usd + cd ≤ Vsd + Xsd + cd with the additional requirement that d ≤ D̃. Therefore, it is sufficient to consider the event where Ul̃∗ − Vsd ≤ Xsd + cd. Since Ul̃∗ is lower-bounded by V ∗ − cD̃, it suffices to consider the event of V
∗ − Vsd ≤ Xsd + cd + cD̃. Therefore the sample complexity N of states queried using the value network is upper-bounded by
N ≤ ∑
sd∈S,d<D̃
K · 1 ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0  . Since ∆sd = 0 whenever sd ∈ A(l∗) and |Xsd | ≤ cd under event E , it follows that the expected sample complexity is E[N ] ≤ KD̃+ ∑ sd∈S d<D̃
sd /∈A(l∗)
K·P ∆sd −Xsd − cd − cD̃ ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ − cD̃ ≤ 0  .

heading: 8.4 CONSTANT GAP MODEL
text: The first example we will consider is the constant gap model, where ∆(l) = η for any l 6= l∗, and the noise variables Xd, Xπd are mean-0 Gaussian random variables.

heading: 8.4.1 USING VALUE NETWORK
text: Lemma 1. In the Constant Gap Model, the expected sample complexity for Algorithm 1 is:
E[N ] = KD + D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(η −X(d−j) − c(d−j) ≤ 0)  . This translates to a sample complexity of E[N ] ≤ KD +D2(K − 1)Kc, for some constant c that satisfies ησc − √ c ≥ √ 2 logK.
Proof. For A?MCTS-V ∗, Algorithm 1, Theorem 1, the sample complexity E[N ] = KD+ ∑
sd∈S,sd /∈L,sd /∈{A(l∗)
K·P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  , is easy to evaluate, because the individual events ∆sd −Xsd − cd ≤ 0 and ∆sd′ −Xsd′ − cd′ ≤ 0 are independent. We claim that
∑ sd∈S,sd /∈L,sd /∈{A(l∗) K · P ∆sd −Xsd − cd ≤ 0 ⋂ sd′∈A(sd) ∆sd′ −Xsd′ − cd′ ≤ 0  is equivalent to
D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(η −X(d−j) − c(d−j) ≤ 0)  . (2) To see why this is the case, we can reason about the first few levels. At depth d = 1, we choose to expand a state with probability P(η −X1 − c1 ≤ 0). There are K − 1 states s1 where s1 /∈ A(l∗).
If we expand a particular node, the sample complexity is K. Therefore the expression would be (K − 1)(K) · P(η −X1 − c1 ≤ 0). At depth d = 2, there are (K − 1)(K) states whose depth 1 ancestor is not in A(l∗). For these states, we choose to expand each with probability P(η −X2 − c2 ≤ 0)P(η −X1 − c1 ≤ 0). The sample complexity for each expansion is K, so in expectation, we query (K − 1)(K2)P(η −X2 − c2 ≤ 0)P(η −X1 − c1 ≤ 0) states. There are also K − 1 states who are not in A(l∗) but their parent in depth 1 are in A(l∗), and we expand them with probability P(η −X2 − c2 ≤ 0). For these states, we query (K − 1)(K)P(η −X2 − c2 ≤ 0) states in expectation. Continuing this reasoning through for depths 3, . . . D − 1 yields the final expression in Equation 2. Therefore the expected sample complexity is:
E[N ] = KD + D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(η −X(d−j) − c(d−j) ≤ 0)  . We can rewrite the above as:
E[N ] = KD + D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(X(d−j) ≥ η − c(d−j))  . which is equivalent to:
E[N ] = KD + D−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP ( Z ≥ η σ(d−j) − √ (d− j) ) ,
where Z is the standard normal distribution.
Standard tail inequalities gives us that P(Z ≥ t) ≤ 1t 1√ 2π e−
t2 2 ≤ e− t 2
2 , where the last inequality holds for t > 1.
We are interested in a value for t such that e− t2 2 ≤ e− logK . This is achieved when t = √ 2 logK.
For exponentially decaying standard deviation as a function of depth, i.e., σd = 1αd for α > 1, when η · α(d−j) − √ d− j > t, P ( Z ≥ ησ(d−j) − √ (d− j) ) ≤ 1K .
Since α, and K are constants, there exists a constant c such that η · α(d−j) − √ (d− j) ≥ √ 2 logK
whenever d− j ≥ c. Therefore, the sample complexity is bounded by:
E[N ] ≤ KD +D2(K − 1)Kc (3)
which is polynomial in the depth D.
For polynomially decaying standard deviation as a function of depth, i.e., σd = 1dα for α > 1, when η · (d− j)α − √ d− j > t, P ( Z ≥ ησ(d−j) − √ (d− j) ) ≤ 1K .
Since α, and K are constants, there exists a constant c′ such that η · (d− j)α − √ (d− j) ≥ √ 2 logK
whenever d− j ≥ c′, and a similar sample complexity to Equation 3 holds.
8.4.2 δ-APPROXIMATE VALUE ESTIMATION
The above reasoning generalizes naturally to a δ-approximate value estimation using A?MCTS-V̂ , Algorithm 3, and the expected sample complexity is:
E[N ] = KD̃ + D̃−1∑ d=1 d−1∑ i=0 (K − 1) i∏ j=0 KP(η −X(d−j) − c(d−j) − cD̃ ≤ 0)  .

heading: 8.4.3 USING VALUE AND POLICY NETWORK
text: Lemma 2. In the Constant Gap Model, the expected sample complexity for Algorithm 2 is:
E[N ] = D−1∑ d=0
( 2 +
K−1∑ k=2 P ( η +X(d+1),1 +X(d+1),k ≤ 2cπd+1
))
+ D−1∑ d=1 d−1∑ i=0
[ 2 +
K−1∑ k=2 P ( η +X(d−i),1 +X(d−i),2 ≤ 2cπd−i )] i∏ j=0 KP(η −Xd−j − cd−j ≤ 0)
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 can 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∑ d=0 ( 2 + K−1∑ k=2 P ( η +X(d+1),1 +X(d+1),k ≤ 2cπd+1 )) .
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∑ k=2 P ( η +X(d+1),1 +X(d+1),k ≤ 2cπd+1 )) .
The second expression can be improved to: D−1∑ d=1 d−1∑ i=0 [ 2 + K−1∑ k=2 P ( η +X(d−i),1 +X(d−i),2 ≤ 2cπd−i )] i∏ j=0 KP(η −Xd−j − cd−j ≤ 0) .
To see why this is the case, we can reason about the first few levels. At depth d = 1, we choose to expand a state with probability P(η −X1 − c1 ≤ 0). There are K − 1 states s1 where s1 /∈ A(l∗),
but in expectation we only consider 2 + K−1∑ k=2 P ( η +X(1),1 +X(1),2 ≤ 2cπ1 ) 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, so the sampling criteria using probabilities from the policy network will always be met. Therefore the expression would be[ 2 +
K−1∑ k=2 P ( η +X(1),1 +X(1),2 ≤ 2cπ1 )] (K) · P(η −X1 − c1 ≤ 0).
At depth d = 2, there are in expectation [ 2 +
K−1∑ k=2 P ( η +X(1),1 +X(1),2 ≤ 2cπ1 )] (K) states
that we would consider expanding from whose depth 1 ancestor is not in A(l∗). For these states, we choose to expand each with probability P(η − X2 − c2 ≤ 0)P(η − X1 − c1 ≤ 0). The sample complexity for each expansion is K, so in expectation, we query[ 2 +
K−1∑ k=2 P ( η +X(1),1 +X(1),2 ≤ 2cπ1 )] (K2)P(η − X2 − c2 ≤ 0)P(η − X1 − c1 ≤ 0) states.
There are also K − 1 states who are not in A(l∗) but their parent in depth 1 are in A(l∗), and we expand them with probability P(η − X2 − c2 ≤ 0). For these K − 1 states, in expectation,
we have expanded only [ 2 +
K−1∑ k=2 P ( η +X(2),1 +X(2),2 ≤ 2cπ1 )] of them, therefore, we expect
to query [ 2 +
K−1∑ k=2 P ( η +X(1),1 +X(1),2 ≤ 2cπ1 )] (K)P(η −X2 − c2 ≤ 0) states in expectation.
Continuing this reasoning through for depths 3, . . . D − 1 yields the final expression:
E[N ] = D−1∑ d=0
( 2 +
K−1∑ k=2 P ( η +X(d+1),1 +X(d+1),k ≤ 2cπd+1
))
+ D−1∑ d=1 d−1∑ i=0
[ 2 +
K−1∑ k=2 P ( η +X(d−i),1 +X(d−i),2 ≤ 2cπd−i )] i∏ j=0 KP(η −Xd−j − cd−j ≤ 0)
For a δ-approximate value estimate, similar arguments apply to give a sample complexity of:
E[N ] = d′−1∑ d=0
( 2 +
K−1∑ k=2 P ( η +X(d+1),1 +X(d+1),k ≤ 2cπd+1
))
+ d′−1∑ d=1 d−1∑ i=0
[ 2 +
K−1∑ k=2 P ( η +X(d−i),1 +X(d−i),2 ≤ 2cπd−i )] i∏ j=0 KP(η−Xd−j − cd−j − cD̃ ≤ 0).

heading: 8.5 GENERATIVE MODEL
text: 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 Vs0 = V
∗ at the root s0. Given the value function of a parent node p, the value functions for the children r1, . . . , rK 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 ri has a value function Vp − Y with Y sampled independently from ∼ U [0, η], the uniform distribution over the interval [0, η]. At level d, there are exactly ( d t ) (K − 1)t states with value function distributed according to V ∗− (Y1 + . . .+Yt). When t is non-negligible, Y1 + . . .+Yt concentrates at constant value tη/2 by the concentration of measure phenomenon.
Using value networks. Let us consider the expected complexity of Algorithm 1 for this model. In the algorithms, cd = C̃ √ dσd for some constant C̃. Following the estimate in Theorem 1, the overall complexity can be bounded up to an extra KD term by D∑ d=1 d∑ t=0 ( d t ) (K − 1)tP ( Xd ≥ ηt 2 − cd ) = D∑ d=1 d∑ t=0 ( d t ) (K − 1)tP ( Z ≥ ηt 2σd − C̃ √ d
) where Z is a standard normal distribution. The goal is to bound this by a quantity polynomial (rather than exponential) in D when η, K, and α are considered fixed. To proceed, we introduce T (d) = 2( √ 2 logK+1) √ dσd
η . For any t ≥ T (d), P ( Z ≥ ηt
2σd − C̃ √ d
) . e− logKd = K−d.
Therefore, for a fixed d, d∑
t=T (d)
( d
t
) (K−1)tP ( Z ≥ ηt
2σd − C̃ √ d
) ≤ d∑ t=T (d) ( d t ) (K−1)tK−d ≤ d∑ t=0 ( d t ) (K−1)tK−d = 1.
Therefore, up to a term linear in D, the sample complexity can be bounded by
D∑ d=1 T (d)∑ t=1 ( d t ) (K − 1)tP ( Z ≥ ηt 2σd − C̃ √ d ) . (4)
Notice first that P(Z ≥ ηt2σd − √ d) is always bounded by 1. Second, since in both the exponential and polynomial noise models σd decays faster than 1/ √ d asymptotically, T (d) = 2( √ 2 logK+1) √ dσd
η
is uniformly bounded by a constant C(K, η, α) due to the exponential decay in d. Therefore, the term (4) can be bounded by (DK)C(K,η,α), which is polynomial (rather than exponential) in the depth D.
Using value and policy networks. Let us consider now the expected complexity of Algorithm 2. Following the argument of the constant gap model, it can be bounded by
D∑ d=1 T (d)∑ t=1 ( d t ) (K − 1)t−1 [ 2 + K−1∑ k=2 P ( η +Xπt,1 +X π t,2 ≤ 2cπt )] P ( Z ≥ ηt 2σd − C̃ √ d ) ,
which is also polynomial in D as it improves over the complexity of using just the value network.
Approximating V ∗ using value and policy networks. For a δ-approximate value estimate using a value network, one can stop early at level D̃ instead and the complexity analysis gives a bound
D̃∑ d=1 T (d)∑ t=1 ( d t ) (K − 1)tP ( Z ≥ ηt 2σd − C̃ √ d ) = O((D̃K)C(K,η,α)).
For a δ-approximate value estimate using both policy and value networks, one can stop early at level D̃ instead and the complexity analysis gives a bound
D̃∑ d=1 T (d)∑ t=1 ( d t ) (K − 1)t−1 [ 2 + K−1∑ k=2 P ( η +Xπt,1 +X π t,2 ≤ 2cπt )] P ( Z ≥ ηt 2σd − C̃ √ d ) .

Review summaries:
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.

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.