Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes an RL-based method to learn the causal ordering of variables. Specifically, it formulates the ordering search problem as a Markov decision process, and then uses different reward designs to optimize the ordering generating model. Compared to [1], which uses RL to search in the DAG space, the proposed method is more efficient. 

Pros:
1. The presentation is easy to follow. 
2. The experimental results seem promising. 
3. The idea of searching the causal ordering, instead of in the DAG space,  to improve the efficiency is reasonable. 

Cons:
1. However, my main concern is that the proposed method lacks a theoretical guarantee of the identifiability of causal ordering, which is very important in the field of causal discovery. 
2. In addition, on linear data, the authors consider large-scale graphs, e.g., the graph which contains 100 nodes. I am wondering why the graph with 100 nodes is not tested on nonlinear data. 
3. Furthermore, the authors should also report the time complexity in order to show the improvement of efficiency. 

If the authors can solve the above issues, I will increase the score. 

Another point is that I am very surprised at the results shown in Table 2. It shows that ICA-LINGAM achieves the true graph even when there are 100 nodes. I am curious about which implementation the authors use.

[1] Shengyu Zhu, Ignavier Ng, and Zhitang Chen. Causal discovery with reinforcement learning. In International Conference on Learning Representations (ICLR), 2020.


Post-rebuttal:
Thanks for the feedback. Some of my concerns have been addressed, but I am still worried about the consistency issue and how to handle the large-scale problem. 


review_title: Experimental results seem promising, but the method lacks theoretical guarantees of identifiability

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a RL formulation to learn the DAG topological order (and then the DAG structure). The reduced search space enables a better and seemly more efficiently learning than the existing RL baselines. Empirical studies has confirmed the better graph learning accuracy results than the existing RL baseline as well as some non-RL structure learning algorithms. 

Positive:
1. Formulation of RL order search is interesting.  Authors discussed the advantage of order-based approach over the existing RL Algorithms, which is convincing. The motivation hence is clear.
2. Theoretical justification with Prop 1 justified the said order-based approach. 
2. The writing is generally easy to follow. Figure 3 study is appreciated. 

Concerns:

1. it is not accurate to state that the exact algorithms can only handle 20.  For example, B&B in (Campos & Ji, 2011) can handle more than 30 nodes, and GOBNILP can regularly handle unto hundreds of variables. 
2. Prop 1: since the statement of graphs with the same distribution P(X) is made, is faithfulness assumed? 
3.  the output dimension of encoder is d times dimension of s? What is the input dimension of decoder and s hat at each step?
4. Some important ablation study are missing, without them it is hard to judge the exact improvement of each components. For example, what is the performance of the pretrained model when combined with RL-BIC2? Would random sampling order instead of learning it via the proposed approach gives similar performance? How about the orders from other order-based learning approaches (as indicated by authors in the paper)?
5. pre-training model: "consider a scenario where the policy model learned on a data model task is used as the pretrained policy model for other tasks. Such results are demonstrated in Section 5.1" - which part in Section 5.1? how the training datasets are generated? is it generated under the same setting as testing graphs? This seems critical on the evaluation. 
6. It could be beneficial that authors show the proposed approach learns a better order than some methods discussed in the paper (Schmidt et al and others). This is important to evaluate the power of RL based approach, since the post processing step is standard. 
7. Since the method uses complex structures such as transformer, an efficiency comparison with all methods is warranted. Specially considering many methods can be tuned via hyperparameters to obtain better solutions with longer time (such as hidden dimensions of neural methods, acyclicity threshold from NOTEAR based methods).

review_title: Interesting formulation, empirical evaluation raises some questions

final_score: rating: 5: Marginally below acceptance threshold
review_content: Update: I have read the authors responses and am happy that they have addressed some of my concerns in my review, especially comparisons with previous works. However, I still have the concern that the improvement seems very minor compared to previous works. Thus, I decide to keep my score unchanged.

Original review:

In this paper, the authors proposed a new RL based algorithm to discover causal DAG models from observational data. Unlike the previous RL based causal discovery algorithm that performs causal discovery via searching through DAG space, it propose to instead search through the smaller ordering space, thereby achieving better empirical performance.

Cons.

1. Ordering based causal discovery is a well-established field. In addition to the empirical findings cited in this manuscript, there are also [1,2] that theoretically understand ordering based causal discovery. New algorithms have also been proposed in the two papers. The authors should cite and compare against the two research works from both theoretical and empirical perspective, which is not the case in the current manuscript.

2. In the variable selection part, since the algorithms perform multiple hypothesis testing, the p-values should be adjusted (such as bonferroni correction) accordingly to adapt to the multiple testing setting.

3. Proposition 1 is trivial and has been proven / taken as known knowledge in many other places, such as [1].

4. The methodological improvement seems not very novel, RL based causal discovery method and ordering based method have both been intensively studied before, and combining them together seems not a very exciting improvement from my perspective.

[1] https://arxiv.org/abs/1702.03530
[2] Bernstein, Daniel, et al. "Ordering-based causal structure learning in the presence of latent variables." AISTATS 2020
review_title: Minor improvement

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper describes an RL approach for DAG structure learning. In particular, the RL agent explores the space of permutations instead of space of adjacency matrices. The experimental results suggest superior performance in a few synthetic data settings. 

Pros: 
- Using RL for causal discovery is gaining popularity recently. But to the best of my knowledge this paper is the first to search over the space of variable orderings, instead of directly searching over the space of DAGs. 
- The experimental result seems to show a significant performance improvement compared to other baselines. 

Cons:
- The superior performance requires some explanation. For instance, there are many design choices made for the model, but it is hard to see which part of the model has brought the performance gain. It would be nice to see some ablation study. 
- Compared to the baselines, this paper proposes a substantially more complicated model. It is surprising that it does not overfit. But it would be nice to see some justifications (other than better TPR, SHD). 


Detailed comments: 
This is a well written paper, but I would need more information to better evaluate it. 
- The RL formulation requires more explanation. For instance, why does the state s_j really represent? Why initialize s_0 with average states? Why does the state encoder use attention networks? What is the role of state transition, if all states depend on all X? 
- More diverse set of experiments would be useful: different density, different topological properties, different noise variances, and different nonlinearities, etc.
- Since the architecture is substantially more complex than baselines, it would be nice to include computational costs like runtime. 
review_title: review

Meta-review: In this paper, the authors propose an RL-based method for learning DAGs based on searching over causal orders instead of graphs. Order search for learning DAGs is a well-studied problem, and it is well-known that this can relieve some of the burden of searching through the space of DAGs. Several reviewers raised legitimate concerns regarding the experiments,  and without identifiability or theoretical results to advance the state of the art, the contribution of this work is limited.
Decision: Reject