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.
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.
Pros:
This 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.
Cons:
However, there are several issues that should be addressed including the presentation of the paper:
•	The 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.
•	Many 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?
•	The 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.
•	The 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”).
 
Other comments:
•	It 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?
•	In fact, the proof of the theorems could be moved to appendices.
•	In the first paragraph of Section 6.2, there is a typo: V*=V_{l*}=\eta should be V*-V_{l*}=\eta ?