Efficient Algorithms for Causal Linear Identification and Sequential Imitation Learning

Finding cause and effect relationships is one of the quintessential questions throughout many of the empirical sciences, AI, and Machine Learning. This dissertation develops graphical conditions and efficient algorithms for two problems, linear identification and imitation learning. For the first problem, it is well-known that correlation does not imply causation, so linear regression doesn’t necessarily find causal relations even in the limit of a large sample size. Over the past century, a plethora of methods has been developed for identifying interventional distributions given a combination of assumptions about the underlying mechanisms (e.g., linear functional dependence, causal diagram) and observational data. We characterize the computational complexity of several existing graphical criteria and develop new polynomial-time algorithms that subsume existing disparate efficient approaches. The proposed methods constitute the current state of the art in terms of polynomial-time identification coverage. In words, our methods have the capability of identifying the maximal set of structural coefficients when compared to any other efficient algorithms found in the literature.

The second problem studied in the dissertation is Causal Sequential Imitation Learning, which is concerned with an agent that aims to learn a policy by observing an expert acting in the environment, and mimicking this expert's observed behavior. Sometimes, the agent (imitator) does not have access to the same set of observations or sensors as the expert, which gives rise to challenges in correctly interpreting expert actions. We develop necessary and sufficient conditions for the imitator to obtain identical performance to the expert in sequential settings given the domain’s causal diagram, and create a polynomial-time algorithm for finding the covariates to include when generating an imitating policy.