Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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. 

In 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. 


review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 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 ?
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: 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.
The 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.

The authors consider a very restrictive setting: 
- Finite horizon Markov decision tree:  no backtrack 
- No intermediate reward and only reward at the end of the episode.
- Deterministic transition
- Importantly, access to value network that gives noisy estimates of the optimal value function 
- The noise model is additive and i.i.d and satisfies a concentration inequality

All 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.
In 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.
review_title: Official Blind Review #2

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