Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a novel extension of MCTS to tackle stochastic state transitions with infinite support. It does so by leveraging the geometry of the state space to "abstract" "similar" states together during the tree building phase. Abstraction refining is introduced to assure that in the limit of infinite samples, the search-tree converges to the full tree, by introducing a schedule on the maximum abstraction distance, based on the number of samples observed.
The authors provide a proof of asymptotic convergence of abstraction refining in the policy evaluation setting.
A brief discussion is done on the choice of distance function to employ during the state abstraction.
Finally, an experimental campaign is conducted in several evaluation and control tasks, that show that abstraction refining consistently outperforms it's main competitor (progressive widening) in handling stochastic transitions with infinite or very large support.
main_review: The authors tackle the really important topic of planning in environments with stochastic transitions and infinite next-state support. The introduce abstraction refining, as a way to progressive build the full (infinite) search tree, by leveraging the geometry of the state space. 
The authors, mainly compare their work, with progressive widening, the only method (apart from open-loop planning) able to tackle these kind of problem. 
They provide a proof of convergence in the policy evaluation case, but do not provide a proof of convergence in the control case, which is a disadvantage compared with progressive  widening, which when used together with UCT, for an appropriate choice of schedule for the \alpha parameter is shown to converge [1].

The authors provide a brief consideration of the additional computational costs of the method which show a limited additional cost, based on the dimensionality of the state space (or learned feature space) used to compute the distance.

The authors provide some experimental results both in the policy evaluation and in the control settings. The proposed method consistently shows better results than progressive widening in all the baselines. Nevertheless, the choice of baselines seems rather odd. While some simple baselines are chosen to study in detail the performance of abstraction refining (like the toy MDP, and the Trap environment), the authors also evaluate in a more complex scenario of 5x5 GO, which intrinsically has no stochasticity, bu the stochasticity is induced by considering the environment as a single player, and fixing the stochastic policy of the opponent. While this makes the environment stochastic, it still does not capture the main contribution of the paper, the capacity to handle larger (or infinite) branch factors of the tree, since the authors report that the best performing algorithm in this setting was Vanilla MCTS (in the appendix) and they were force to introduce an additional source of stochasticity to require the use of PW or AR. 
The authors have a brief discussion of the choice of distance measure, since it is a crucial component of AR, but a more thorough experimental campaign is needed. Three of the presented domains, were simple enough to use Euclidean distance. In the 5x5 Go, the distance was employed on a learned state embedding, and nevertheless failed to improve on vanilla MCTS without an additional noise. 

I think the paper tackles an extremely important problem but more careful consideration of the distance measures needs to be adressed, at least experimentally.
[1] Adrien Couetoux. Monte Carlo Tree Search for Continuous and Stochastic Sequential Decision Making
Problems. Data Structures and Algorithms [cs.DS]. Université Paris Sud - Paris XI, 2013.

======== Update ==≠====
 I have had a thorough discussion with the authors, during which the authors have agreed to the limitations that I pointed out, and also have conducted some experiments that demonstrate these limitations. In my opinion, it is ok to have limitations but they should be made clear, and especially better if demonstrated empirically. As a result, I will raise my score from 5 to 6, but this if the authors include a final experiment promised in the last rebuttle. While I am aware that as reviewers we cannot enforce the addition of the experiment, the authors have already made 3 new experiments during the rebuttle so I would be inclined to 'trust' the authors for this final experiment.
limitations_and_societal_impact: Main limitation is:
The need for a carefully thought distance measure.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors present MCTS with abstraction refining based on the nearest neighbor algorithm.

main_review: MCTS has been a topic of interest in the AI/Machine Learning community over a decade and the authors address an important issue about MCTS. The paper is understandable with some interesting results. However, I have the following comments some of which could be clarified in the rebuttal phase:

1. If I understand the algorithm correctly, how states are abstracted depends on the order of states selected during iterations of MCTS. I wonder how robust abstract refining is due to different orderings of the states.

2. Some researchers have worked on MCTS with state abstractions. Particularly, the following paper might be related to the task they address. I wonder why iterative abstraction refinement was not compared against it. 

Jesse Hostetler, Alan Fern, Thomas Dietterich. "Sample-Based Tree Search with Fixed and Adaptive State Abstractions", JAIR 2017. 

https://jair.org/index.php/jair/article/view/11096

3. AlphaZero does not account for the size of the territory once a position is likely to be a win/loss -- it only cares about whether to win or loss. Therefore, it is not a good idea to evaluate the algorithm performance based on the territory size. Also, in my understanding, AlphaZero is not combined with search in section 4.4. If this is correct, what would the performance comparison be like if AlphaZero is combined with search? 

Miscellaneous

The authors should check the captions in the references (e.g,  Monte Carlo Tree Search which is currently with lowercase). 

UPDATE
------------
Thanks for your response. I had discussions with other reviewers and am happy to increase my score. 


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method, called abstraction refining, for extending MCTS to stochastic environments that leverages the geometry of the state space. Compared to progressive widening with global hyperparameters for every state, abstraction refining groups the states together dynamically depending on each state. Their results show abstraction refining outperforms progressive widening in the way of their experiments of this paper.
main_review: While it is interesting for the proposed method to reduce the large search space like progressive widening, there are the following major concerns. 
This paper gives four examples in the experiments, but experimental analyses are most based on value errors. It is not convincing in this way since the most important criteria for MCTS is the strength, not just value errors. This paper still needs more experiments including the strength to demonstrate the idea is working.  
In addition, in these examples, the nearest neighbors are calculated all based on the geometry of state  space (or Euclidean distance). It is very hard to convince people to believe that this would work for some games, like Go. This paper mentions we could use better distance functions for the nearest neighbors in the Discussion section; however, actually, it is the most important work that this paper needs to do to showcase the excellence of their method. 
The proposed idea for grouping state by abstraction refining to reduce the branching factor is somewhat similar to [11], which is applied to many continuous action space problems. What’s the main difference between the presented method and their work? A continuous action space can also be viewed as a large action space problem. 
This paper tries to justify the computation cost for the nearest neighbor in the last paragraph of Section 3.2, where the cost is derived to be O(log p) or O(log num_children[s, a]) in the parallel time complexity based on the assumption of unlimited (or a large number of) processors. Unfortunately, this assumption is strange and not realistic. It is more important and interesting to justify it through experiments. 


Other comments:
The abstraction refining hyperparameters (epsilon_n) are quite different in each experiment. Why? Any guideline to set the hyperparameters? Or, it is a need to do more experiments for different epsilon_n in abstraction refining?
It is also required to analyze the branch factor for abstraction refining and progressive widening for each experiment. 

About presentation:
* In line 176, c in R_{s’’}^{c} is undefined. 
* What is the epsilon_n used in five by five Go? BTW, it is suggested using “5x5 Go”. 
* Some typos:
** Line 40: and and -> and
** Line 98: determinstic -> deterministic
** Line 147: pseuodocode -> pseudocode

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper generated a good amount of discussion between the authors and reviewers, which helped resolve some issues in the original reviews. Certain issues remain, but the paper does seem to be making a reasonable and novel contribution in light of those issues. 

The reviewers have worked hard to suggest improvements and the authors have already indicated the inclusion of new experiments and adjustments to the text. It is expected that the authors will follow through on these promises. 

Finally, I would like to point out that the authors have not properly characterized the related paper pointed out by one of the reviewers.

Jesse Hostetler, Alan Fern, Thomas Dietterich. "Sample-Based Tree Search with Fixed and Adaptive State Abstractions", JAIR 2017

The authors indicate in their response that the paper assumes more than a sample-based model, but that is not accurate. It does not assume access to the entire set of next states. Also note that the algorithm in the experiments of that paper is based on forward-search sparse sampling, which is a trajectory-sampling algorithm in the spirit of MCTS/UCT. Thus a modification to MCTS is not as distance as the authors may think. 
Decision: Accept (Poster)