Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work presents an approach for learning state-action abstraction in stochastic shortest path problems (SSPs). The paper introduces  Generalized Policy Automata (GPA), which are hypergraphs wherein edges representing abstract actions connect a start abstract state to some set of destination abstract states. Given a planning domain described in a symbolic description language, the paper proposes to automatically learn a GPA on small instances of a given planning domain, and then use the learned GPA to accelerate planning with an off-the-shelf SSP solver in new, possibly larger, problem instances. This is done by pruning state transitions that don't correspond to any hyperedge in the learned GPA, thus reducing the amount of computation needed. If the pruned version of the problem cannot be solved, the algorithm resorts to planning with the original problem. The authors analyze some of the theoretical properties of the method. Finally, experimental results show that the proposed approach can accelerate state-of-the-art SSP solvers in a number of planning domains represented in the PPDDL symbolic language. 
strengths_and_weaknesses: **Originality** 

The proposed approach builds on a well-known notion of abstraction (canonical abstraction), but the proposed approach for learning and using GPAs is new, to the best of my knowledge. On the other hand, the idea of learning a sparse representation of planning problems in small instances and apply on larger instances has been explored before (see [1] below for an example), so the main novelty of this work lies in the use of GPA for this, and the completeness guarantees. 

-----
[1] Pineda, L.E. and Zilberstein, S., 2014, May. Planning under uncertainty using reduced models: Revisiting determinization. In Twenty-Fourth International Conference on Automated Planning and Scheduling.

**Quality** 

The proposed approach is sound, and the theoretical properties look correct to me. I have some concerns about the experiments. One is the choice of problems, which seems a bit arbitrary, considering that they are different than those used in other recent work, including the Soft-FLARES baseline, but also in ASNets by Toyer et al., 2020, and Karia Srivastava, 2021. 
I also have some reservations about the hyperparameter tuning for Soft-FLARES. In the appendix it is mentioned that $t=4$ was selected, but this choice is not motivated. A look at the Soft-FLARES paper suggests that this parameter has strong impact on performance, and that policies of similar quality can be obtained faster with lower values of $t$, which would possibly decrease the perceived benefits of the GPA-based approach. Again, stronger motivation for this choice should be offered. 

**Clarity** 

The paper is reasonably well-written and the flow of ideas in the paper seems natural; the running example was also helpful. On the other hand, the paper is notation-heavy and somewhat dense, and it took a number of careful reads before I was confident that I understood the proposed approach. It would be helpful for readers to start with a high level overview of what the proposed technique is, without using any of the formal definitions, preferably including an image/diagram to illustrate how it works. I think the basic idea is intuitive enough that such an explanation is possible, but it's currently hidden under a dense layer of formalism. 

**Significance** 

I think the proposed approach is interesting and relevant to the probabilistic planning community. The experiments show that, when a symbolic model of the environment is available, the proposed approach can be beneficial in terms of solution quality and computation time. That being said, the applicability of this approach is limited to having a symbolic model of a problem available, which I'd argue it's often a harder problem than planning itself. Indeed, the statement in line 21 about human-engineering effort can also perfectly be applied to building a symbolic model, so I'd be wary to offer this as a strong motivation in favor of this approach. One advantage of deep-learning based approaches is precisely that it avoids human effort spend in hard-coding a good representation for the task at hand. 
questions: Considering the discussion above, my main questions are:

- Can you motivate the choice of evaluation domains? How does your method perform in other SSP problems described in PPDDL that are commonly used (e.g., triangle tireworld or exploding blocksworld).

- How were the hyperparameters for Soft-FLARES chosen?

- Other recent approaches such as ASNets (Toyer et al., 2020), which is mentioned in the introduction, would also be relevant for this problem and not included in the evaluation. Can you elaborate on why this choice was made? Similarly, a natural baseline to include whenever pruning is used in PPDDL domains is a determinization-based approach, which ofter perform surprisingly well. The reference [1] above does this by learning a promising determinization in small problem instances, similarly to how the proposed approach does it. Is there a reason why this comparison is not applicable here?
limitations: The authors discuss several limitations of the approach in Section 6. I think it would also be important to include some discussion regarding the limitations I mentioned under "Significance" above.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a learning algorithm for a class or relational stochastic shortest path problems. The algorithms specialized in relational domains where states have meaningful factors out of named relationships -called predicates– and objects. Using previous ideas for generalized planning, the algorithm defines a new cost function for the original problem that assigns infinite cost to transitions not properly rendered in the abstraction. Such a problem is used to obtain a policy using an existing algorithm. If that policy is proper, that could be returned. Otherwise, the values of the previous algorithms can be used to solve the problem with the original cost.
In summary, the algorithm synthesizes a generalized policy automata (GPA) and attempts a solution to the global problem using its cost.
strengths_and_weaknesses: The strongest points of the paper are:
- Use of abstraction previously used for deterministic domains.
- Clear characterization of what the generalization means.
- Low-data requirements
- Clearly significant empirical results

Weakness
- The paper is built around the assumption that what matters is the accuracy in comparison with other algorithms that attach the problem directly. That leads to not-so-surprising statements like theorem 3.2, as its proof applies to any algorithm that generates a candidate of the solution, returns it if it works, and falls back to a more complex solution.
- The notion of canonical abstraction is not explained enough to understand the scope of the technique. The example right before 3.3 offers some ideas but I would not expect users unfamiliar with the previous work on generalized planning to understand that. The domains would have presented an opportunity to describe what the GPA is doing in those cases.
- The canonical abstraction depends strongly on the relational domain.

In my opinion, the strengths outweigh the weakness. The paper is presented as an empirical algorithm, so it makes sense to focus the evaluation on existing tasks. I would have say that understanding the expressivity of the GPA is important and beyond the scope of the paper.

Some additional comments:
- please revise this paragraph: *Highlight [page 4]:* Given a predefined set of abstraction predicates, canonical abstractions group together different objects based on the subset of abstraction predicates that they satisfy in a state. Each subset of abstraction predicates is known as a summary element
- Why? *Highlight [page 4]:* An object o belongs to exactly one summary element in any given concrete state s and this is the maximal summary element for that object.

questions: 1. How can this be used in domains where there are no unary predicates? For instance, suppose a graph that has proportional in the edges for not in the nodes. Each proposition can be seen as a binary predicate over the notes.
2. In the experiments, 
	2.1. How frequently was the policy using the GPA proper? 
	2.2. In that case, how much is gained by running the full algorithm?
	2.3. In the domains, how many costs changed to $\infty$ because of the GPA
3. Please, elaborate on the relationship between the submission and "Learning generalized relational heuristic networks for model-agnostic planning. In AAAI, 2021.?
4. In problems with the same GPA, could policy could be used directly?

limitations: I think the paper comments enough about the technical limitations. This is a well-defined class of problems, and their solutions are strictly algorithmic with predictable properties.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces the concept of generalized policy automata (GPA) to speed up the solution of stochastic shortest path problems (SSPs), defined here within a more general AI Planning perspective. The intuition is to leverage GPAs within a "learn-from-small-examples" framework, i.e., they capture the (abstract) states and optimal controls of small instances (the "training" set), and are subsequently used in a GPA-accelerated SSP solution (specifically, by adjusting the SSP cost function accordingly). Numerical results evaluate the approach on classical planning benchmarks. 
strengths_and_weaknesses: Strengths
- Innovative structure to capture knowledge associated with optimal controls
- Good computational results for the domains tested

Weaknesses
- In my view, limited analysis or discussion of why and when the method is effective
- Numerical results seem quite restricted

Major Comments

In general, I greatly appreciated the GPA concept; I found it to be innovative and overall intuitive to understand, as essentially it projects the original system to a smaller (abstract) set of states and actions. The results for the four planning domains tested are also promising, especially when evaluating the results for Keva and Rover. However, I have two major concerns associated with the methodology and the numerical study.

(i) [Methodology.] I believe my major question, perhaps due to some misunderstanding on my part, is fundamentally "why would this method work?" More precisely, there is little intuition presented on when the small instances have enough information to capture good controls, or why that should always the case. What are the underlying properties of SSPs that motivate heuristics based on small optimal portions, and when (or if) would this break? Could it be the case that this information is "deceiving," in that larger problem instances have significantly different controls (e.g., Gripper)? 

While I understand that the analysis is a more computational proof of concept, I felt that any intuition, such as through more informative examples, would be quite effective in demonstrating why the approach is effective.

(ii) [Numerically.] Related to point (i), the numerical study essentially focuses on a horse-race comparison between approaches in terms of time and solution cost. However, I believe that for such a new idea there are other metrics that could be as important as the total runtime for drawing insights. For example, the training setup is rather limited (only ten instances!) - is there any gains in increasing the learning period? If not, why would that be the case? Furthermore, are there any properties of states that the policy was more "accurate" with respect to the optimal control?

Overall, I enjoyed the idea but feel that a more extensive numerical analysis is critical to this work, again to shine light into when the method could be most effective. 

questions: 1. Is it possible to incorporate more examples of the type of learning that is being performed by the approach?

2. Do the authors have any (theoretical) intuition on when learning from small examples in this particular context is effective? What is the fundamental structure of the smaller instances that is preserved in larger problems for this approach to be successful?

3. Are there any gains if more time and instances are allotted to the training set? Is there any risk, for example, of an "oversampling" in this context? (I believe not because of Theorem 3.3?)


limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors propose an approach to learning Generalized Policy Automata (GPA) so as to accelerate the solution process of Stochastic Shortest Path Problems (SSP). GPAs are a non-deterministic finite-state automata that compactly encodes generalized knowledge. Furthermore, GPA imposes hierarchical constraints on the state space of the SSP and prunes the considered action space. To learn GPA, they group different objects through a canonical abstraction, and then iteratively compute GPA from a small training set containing solutions like SSP instances. Finally, they theoretically proved that the method has completeness and hierarchical optimality. Experimental results also verify that the method significantly outperforms state-of-the-art SSP solvers.
strengths_and_weaknesses: Originality：
(1) Compared with other methods, the method of this paper can automatically construct the GPA without any human intervention. In addition, canonical abstractions are used to extract problem-specific features such as object names and object counts.
(2) Another key difference from other techniques in existence is that the authors' method can easily incorporate solutions from new examples into the controller without having to remember any earlier examples, leading to better scalability of GPA learning.

Quality：
(1) I find that the overall structure of the paper is good, that leverages clear method structures, exhibits comprehensive comparison to related work and builds up reasonable comparative experiments.
(2) As I said above, the overall structure of this paper is good. However, the position where the evaluation criteria appear is not very appropriate. They should be introduced at the beginning of the experimental section, which will make the whole experimental process more reasonable.

Clarity:
(1) The overall meaning of this paper is transparent, most of the methods are well explained, and the theorems are clearly proved.
(2) Although the paper contains examples, but there is only a lengthy description in the section “Canonical Abstraction”. The work would benefit by including some clear, illustrative pictures into the main body of the paper, to better motivate and illustrate the work.

Significance：
In my opinion, this paper addresses an interesting research topic where they exploit knowledge from solutions of SSP instances with small object counts to learn GPAs that allow effective pruning of the search space of related SSPs with larger object counts. This ability is essential for solving stochastic shortest path problems because of its excellent generalization ability and solution efficiency.

questions: (1) You mentioned in the Solving SSPs using GPAs section that there is no abstract translation in general policy automata (line 228). When does this phenomenon happen? In addition, if it happens, does it cause the SSP solver to have no speedup or even less efficient?

(2) In the experimental section, you only used a small training set when learning GPA, and finally got very good results. If you continue to increase the number of training sets, will the experimental results gain a significant improvement?

(3) As I mentioned earlier, this paper can be better comprehensive by adding some explanatory pictures for some complex contents (such as the section on "Canonical Abstraction") and illustrating the statement of experimental standards in priority.
limitations: In my opinion, the authors fail to mention some limitations of their approach in the article, which may overlook some potential problems. As the authors mention in the section "Solving SSP with GPA", there is no abstract translation in the general policy automata (line 228). If this happens frequently, it may affect the effectiveness of their approach. Therefore, I think this is a limitation worthy of further consideration.
review_title: null

Meta-review: metareview: While the paper's approach is applicable only to MDPs with a known relational model expressible in the PPDDL language, the reviewers unanimously find it to be an interesting, novel advance for this class of settings.
confidence: Certain
Decision: Accept