Summary
The paper highlights the limitations of the conventional method for learning heuristics in search algorithms, which involves imitating the optimal cost-to-go function. The authors present an alternative approach that focuses on optimizing the correct ranking of state pairs by the heuristic. Because of that characteristic, the authors argue that the resulting heuristic offers both theoretical and practical advantages compared to the standard approach.
Weaknesses
In my opinion, the claims formulated in the paper should be supported better. I'm not convinced that the reported results stem from the theory. Clearer discussion of theoretical advantages and disadvantages of various approaches, more detailed experiments including analysis of the learned heuristic, and comparison with some other baselines could be a significant improvement to the paper. Details of my concerns are discussed in the comments.
Questions
In general, I like the idea and the paper, although at this point it may need some improvements. At this point I'm not fully convinced that the improvement you show is due to the theoretical advantages (which should be clarified) or just a fancy heuristic that happens to work better than a certain imitation objective. Below I highlight a few specific comments.
- l.111,117,157 Arguably a central expression, appears in 3 places, and every time is written differently. Correct it (or explain that it's actually not the same).
- l.113-125 This explanation of the notation above is a lifesaver.
- l.131 Does there exist at least one perfect ranging for every problem? Semms that h(s):=[-infty on a fixed optimal path, infty otherwise] works. What happens in quite a common case in which s_0 is not specified and the heuristic should work for any starting state? Does there always exist a perfect ranking in such case?
- l.105-150 While I don't deny the soundness of the theory, it reads a little like explaining quite an intuitive idea ("the heuristic is strictly optimal iff in every step of the search the next node on a fixed optimal path receives the lowest value") with very complicated expressions. I'd consider changing the order and starting from intuition, moving to the formalities afterwards. The ultimate conclusion should be the expression in l.111, which I believe is the central object in this section.
- l.161 Quite a strong assumption.
- l.167 The relation between log(1+exp(x)) and [[x>0]] indeed seems loose. On convergence it will have the desired property indeed, but it doesn't exactly optimize the number of violations, rather a sum of violation volumes. How does it relate to your theory? An experimental analysis of the learned function would do.
- l.180 I'd consider rewording the section title. Although after reading the section it makes sense, at first it seems like a general discussion of optimizing neural networks.
- l.181-185 I like the idea, but it's not true that it is easier to learn a function from a bigger class. The core element is the learning signal. In case of cost-to-go, where we have actually a direct supervision, it is of much better quality than in case of a set of inequalities. Consider an example in which we have n states and we want to learn any monotonic function. Although there are much more functions satisfying f(s_{i+1})>f(s_i), learning fixed supervised targets should be faster.
- l.186-196 "states off the solution path" -- you mean in the training dataset or in general? As far as I understand, your training dataset consists of solving paths only, so the issue applies to your ranking loss as well, doesn't it? When provided with off-the-path states, standard cost-to-go functions can also utilize them for learning (e.g. bootstrapping for Q-learning). The issue you describe is devoted to the particular training loss you consider, not learning cost-to-go in general.
- l.203-207 I don't understand. Optimizing the proposed losses never considers dead-ends as they don't lie on the optimal paths. Do you consider any hand-modified heuristics? If you are worried about too high gradients, use Huber loss instead of L2. Why should lare values appear in the training? (5) is strictly supervised.
- l.269 That's a shame, it would support your claims well as it makes a middle-ground between (3) and (5).
- l.285 How costly is it to get this dataset? Is your method more efficient than SymBA* afterwards? Gathering optimal paths for training may be very costly, especially in the hardest domains. Thus, can you comment on the applicability of your claims, since you require a costly operation of gathering optimal paths for your training> Can your method, like standard imitation, learn also from sub-optimal data, which is often much easier to get?
- l.286 Why a single problem instance?
- l.322-342 If the test sets are harder than training sets, how does it relate to the theory in which you assume having optimal paths?
- l.343-363 I'm not familiar with the complexity of some instances of the environments. Thus, it would be helpful to see some trivial baselines in the comparison, such as BFS or Dijkstra. Also, to showcase an advantage of your theory-driven approach, I'd consider comparing with a simple objective that learns to output 0 on the solving paths and 1 on other states outside the path. It fits the definition of optimality and doesn't seem to be stable or generalizable (or maybe?). Advantage over such a baseline would highlight the benefit of learning the ranking over heuristics. It's missing now. Yes, I know that you compare already agains many relevant baselines.
- l.343-363 Also, the claims should be supported by some ablations. Is the learned heuristic correct? Does it learn to properly rank states, even in the training domains? What does it converge to, do the values resemble cost-to-go or some other interpretable quantities? What are the mistakes? Does the learned heuristic fit the theory of what it should learn? Are the paths obtained this way optimal? How do they relate to optimal paths in terms of length? How often only states on an optimal path are expanded? Can you learn a useful heuristic for a fixed domain with many possible starting points?
- l.375 I'm not sure whether optimizing set of inequalities is easier than a direct supervision.
And a few minors:
- l.31,212,215,271 etc. When you refer to something, either in your paper or in supplementary, refer to the exact section.
- l.40 Do you mean "state-of-the-art"?
- l.48 I wouldn't say "always", you can demonstrate that it's better "in those eight environments".
- l.50-72 I can't find a definition of g(s) or h(s) before you use it to explain your algorithm. Maybe in preliminaries? g(s) is defined below the algorithm, but h(s) is not.
- l.116,135, and others: I feel confused whether "heuristic" refers to h or f. Please disambiguate the notation.
- l.305 24000 gradient steps in 100 GPU hours? Seems quite slow, I'd suggest checking it.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.