Summary
This paper extends studies on causal imitation learning to settings in which additional information can be provided in the form of context-specific independences (CSIs). Causal imitation learning seeks to maximize some unobserved reward $Y$ by finding a policy $\pi^*$ from the space of policies $\Pi$ such that the reward distribution under that policy, $P(Y \mid do(\pi))$ matches that of the expert policy, $P(Y)$, thereby mimicking the expert. However, mimicking $P(Y)$ is not always possible in settings with unobserved confounding, so additional knowledge in the form of causal constraints is necessary to decide whether $P(Y)$ is imitable. In prior works where such constraints are assumed in the form of a causal diagram $\mathcal{G}$, it has been proven that $P(Y)$ is imitable if and only if there exists a $\pi$-backdoor admissible set $\mathbf{Z}$ w.r.t. $\langle \mathcal{G}, \Pi \rangle$. However, completeness no longer holds when CSIs are provided, in which further independence information about the distributions may be provided, conditioned on specific settings of the variables. The paper first proves that deciding imitability in this more general setting is NP-hard (Thm. 3.8). Given this limitation, they provide a sound algorithm that checks imitability within each context-induced subgraph, which they prove is also complete under a further assumption (Alg. 1). In settings where this assumption does not hold, they show that imitability can still be achieved if a policy on a set of surrogate variables is identifiable under a specific setting of CSIs. This provides a more general algorithm (Alg. 2), evaluated experimentally.
Strengths
To be fully transparent, I have reviewed this paper in the past, so the following list of strengths and weaknesses reflect my existing impressions of this paper, which I have updated following another read of the latest manuscript. However, my points are largely the same, since I do not see many notable changes in the latest version. Please correct me if I am wrong.
**Strengths:**
1. Problem is well-motivated. LDAGs arise in practice and provide more information than standard causal diagrams, which should be leveraged to allow more imitable cases. This would add more positive results to the causal imitation learning literature.
2. Assumptions are clearly stated. LDAGs are well defined, and the paper does a good job of explaining specifically how the additional constraints are incorporated. The authors are very transparent with the limitations of their approach.
3. The solution is nontrivial and interesting. The paper clearly shows non-imitable cases that are rendered imitable when accounting for CSIs. The obvious solution of checking for backdoor sets in each context-induced subgraph is only complete under a strict assumption.
Weaknesses
I reiterate that these points are similar to the points I made in my previous read of the paper. I have an overall positive opinion of the paper, and my goal is to help improve the paper, so I hope the authors will take this feedback into consideration.
**Weaknesses:**
1. There is nothing done to address the NP-hardness claimed by Thm. 3.8. Alg. 1 and 2 still take exponential time in the worst case. It may be insightful to provide some alternative settings in which assumptions are strict enough that polynomial time solutions can be developed. Alternatively, algorithms that sacrifice completeness for speed could be provided. While I understand that this may be out of the scope of the paper, it is otherwise not clear to me why Thm. 3.8 is relevant to the paper in the first place.
2. Unfortunately, even Alg. 2 is not complete in the general case. Completeness is not a requirement for it to serve as a real contribution, but it would help to have some insights in this paper on why Alg. 2 is incomplete (e.g. some counterexamples) and some ideas on what could be done to move towards completeness.
3. The motivation for Alg. 2 could be improved in terms of clarity. Notably, it could be emphasized why Alg. 1 fails in a more general setting. Eq. 3 could be explained better as well to motivate the idea of context-specific surrogates (I did not really understand Eq. 3 until I derived it myself by hand).
4. The experiments illustrate the point as intended, but the tested scenarios are very limited in scope. The first experiment only studies a specific family of graphs, and the second experiment is performed on one specific SCM. Neither of these choices are justified. While a more extensive empirical study would boost the strength of this work, it would help immensely just to be transparent about the data generating process to ensure that there was no cherry picking. For example, for Sec. 5.1, why were those choices of delta and probability of latent variables chosen? And for Sec. 5.2, why were the parameters for that specific SCM chosen (as described in Appendix C)?
5. Many of the ideas in this paper (including the interesting point about surrogates) incrementally improve existing ideas from Zhang et al. (2020). This reduces some of the novelty.
6. This is a minor point and did not affect my judgment of the score, but on line 261, the authors describe the imitability problem under CSIs using the inputs of $\langle \mathcal{G}^{\mathcal{L}}, \Pi, P(\mathbf{O}) \rangle$ as opposed to $\langle \mathcal{G}^{\mathcal{L}}, \Pi \rangle$. I understand that this is due to the CSI setting requiring additional information in the form of constraints over $P(\mathbf{O})$, but I think this could be better framed. Both the original imitability problem and the new version with CSIs uses $P(\mathbf{O})$, since it must be clear that only observational data is available, as opposed to additional interventional data such as $P(\mathbf{O} \mid do(\mathbf{x}))$, collected from experimentation. In addition to this however, the CSI setting should include a set of independences.
Overall, my impression is that this paper is worth publishing, since everything is well-defined, the proofs make sense, the assumptions are clear, and the claims are sufficiently backed. I believe that a score of 6 is appropriate given the level of contribution of the paper, which is solid but somewhat limited.
Questions
No questions, but would be interested in hearing author responses in case I missed something.
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.
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.
Limitations
Limitations are clearly stated.