Causal Confusion in Imitation Learning

Introduction

Imitation learning allows for control policies to be learned directly from example demonstrations provided by human experts. It is easy to implement, and reduces or removes the need for extensive interaction with the environment during training .

However, imitation learning suffers from a fundamental problem: distributional shift . Training and testing state distributions are different, induced respectively by the expert and learned policies. Therefore, imitating expert actions on expert trajectories may not align with the true task objective. While this problem is widely acknowledged , yet with careful engineering, naïve behavioral cloning approaches have yielded good results for several practical problems . This raises the question: is distributional shift really still a problem?

In this paper, we identify a somewhat surprising and very problematic effect of distributional shift: “causal misidentification.” Distinguishing correlates of expert actions in the demonstration set from true causes is usually very difficult, but may be ignored without adverse effects when training and testing distributions are identical (as assumed in supervised learning), since nuisance correlates continue to hold in the test set. However, this can cause catastrophic problems in imitation learning due to distributional shift. This is exacerbated by the causal structure of sequential action: the very fact that current actions cause future observations often introduces complex new nuisance correlates.

To illustrate, consider behavioral cloning to train a neural network to drive a car. In scenario A, the model’s input is an image of the dashboard and windshield, and in scenario B, the input to the model (with identical architecture) is the same image but with the dashboard masked out (see Fig 1). Both cloned policies achieve low training loss, but when tested on the road, model B drives well, while model A does not. The reason: the dashboard has an indicator light that comes on immediately when the brake is applied, and model A wrongly learns to apply the brake only when the brake light is on. Even though the brake light is the effect of braking, model A could achieve low training error by misidentifying it as the cause instead.

This situation presents a give-away symptom of causal misidentification: access to more information leads to worse generalization performance in the presence of distributional shift. Causal misidentification occurs commonly in natural imitation learning settings, especially when the imitator’s inputs include history information.

In this paper, we first point out and investigate the causal misidentification problem in imitation learning. Then, we propose a solution to overcome it by learning the correct causal model, even when using complex deep neural network policies. We learn a mapping from causal graphs to policies, and then use targeted interventions to efficiently search for the correct policy, either by querying an expert, or by executing selected policies in the environment.

Related Work

Imitation learning. Imitation learning through behavioral cloning dates back to Widrow and Smith, 1964 , and has remained popular through today . The distributional shift problem, wherein a cloned policy encounters unfamiliar states during autonomous execution, has been identified as an issue in imitation learning . This is closely tied to the “feedback” problem in general machine learning systems that have direct or indirect access to their own past states . For imitation learning, various solutions to this problem have been proposed that rely on iteratively querying an expert based on states encountered by some intermediate cloned policy, to overcome distributional shift; DAgger has come to be the most widely used of these solutions.

We show evidence that the distributional shift problem in imitation learning is often due to causal misidentification, as illustrated schematically in Fig 1. We propose to address this through targeted interventions on the states to learn the true causal model to overcome distributional shift. As we will show, these interventions can take the form of either environmental rewards with no additional expert involvement, or of expert queries in cases where the expert is available for additional inputs. In expert query mode, our approach may be directly compared to DAgger : indeed, we show that we successfully resolve causal misidentification using orders of magnitude fewer queries than DAgger.

We also compare against Bansal et al. 2019: to prevent imitators from copying past actions, they train with dropout on dimensions that might reveal past actions. While our approach seeks to find the true causal graph in a mixture of graph-parameterized policies, dropout corresponds to directly applying the mixture policy. In our experiments, our approach performs significantly better.

Causal inference. Causal inference is the general problem of deducing cause-effect relationships among variables . “Causal discovery” approaches allow causal inference from pre-recorded observations under constraints . Observational causal inference is known to be impossible in general . We operate in the interventional regime where a user may “experiment” to discover causal structures by assigning values to some subset of the variables of interest and observing the effects on the rest of the system. We propose a new interventional causal inference approach suited to imitation learning. While ignoring causal structure is particularly problematic in imitation learning, ours is the first effort directly addressing this, to our knowledge.

The Phenomenon of Causal Misidentification

In imitation learning, an expert demonstrates how to perform a task (e.g., driving a car) for the benefit of an agent. In each demo, the agent has access both to its $n$-dim. state observations at each time $t$, $X^{t}=[X^{t}_{1},X^{t}_{2},\ldots X_{n}^{t}]$ (e.g., a video feed from a camera), and to the expert’s action $A^{t}$ (e.g., steering, acceleration, braking). Behavioral cloning approaches learn a mapping $\pi$ from $X^{t}$ to $A^{t}$ using all $(X^{t},A^{t})$ tuples from the demonstrations. At test time, the agent observes $X^{t}$ and executes $\pi(X^{t})$.

The underlying sequential decision process has complex causal structures, represented in Fig 2. States influence future expert actions, and are also themselves influenced by past actions and states.

In particular, expert actions $A^{t}$ are influenced by some information in state $X^{t}$, and unaffected by the rest. For the moment, assume that the dimensions $X_{1}^{t},X_{2}^{t},X_{3}^{t},\dots$ of $X^{t}$ represent disentangled factors of variation. Then some unknown subset of these factors (“causes”) affect expert actions, and the rest do not (“nuisance variables”). A confounder $Z^{t}=[X^{t-1},A^{t-1}]$ influences each state variable in $X^{t}$, so that some nuisance variables may still be correlated with $A^{t}$ among $(X^{t},A^{t})$ pairs from demonstrations. In Fig 1, the dashboard light is a nuisance variable.

A naïve behavioral cloned policy might rely on nuisance correlates to select actions, producing low training error, and even generalizing to held-out $(X^{t},A^{t})$ pairs. However, this policy must contend with distributional shift when deployed: actions $A_{t}$ are chosen by the imitator rather than the expert, affecting the distribution of $Z^{t}$ and $X^{t}$. This in turn affects the policy mapping from $X^{t}$ to $A^{t}$, leading to poor performance of expert-cloned policies. We define “causal misidentification" as the phenomenon whereby cloned policies fail by misidentifying the causes of expert actions.

Intuitively, distributional shift affects the relationship of the expert action $A^{t}$ to nuisance variables, but not to the true causes. In other words, to be maximally robust to distributional shift, a policy must rely solely on the true causes of expert actions, thereby avoiding causal misidentification. This intuition can be formalized in the language of functional causal models (FCM) and interventions .

Functional causal models: A functional causal model (FCM) over a set of variables $\{Y_{i}\}_{i=1}^{n}$ is a tuple $(G,\theta_{G})$ containing a graph $G$ over $\{Y_{i}\}_{i=1}^{n}$, and deterministic functions $f_{i}(\cdot;\theta_{G})$ with parameters $\theta_{G}$ describing how the causes of each variable $Y_{i}$ determine it: $Y_{i}=f_{i}(Y_{\text{Pa(i;G)}},E_{i};\theta_{G}),$ where $E_{i}$ is a stochastic noise variable that represents all external influences on $Y_{i}$, and $\text{Pa}(i;G)$ denote the indices of parent nodes of $Y_{i}$, which correspond to its causes.

An “intervention” $do(Y_{i})$ on $Y_{i}$ to set its value may now be represented by a structural change in this graph to produce the “mutilated graph” $G_{\bar{Y_{i}}}$, in which incoming edges to $Y_{i}$ are removed. For a more thorough overview of FCMs, see .

Applying this formalism to our imitation learning setting, any distributional shift in the state $X^{t}$ may be modeled by intervening on $X^{t}$, so that correctly modeling the “interventional query” $p(A^{t}|do(X^{t}))$ is sufficient for robustness to distributional shifts. Now, we may formalize the intuition that only a policy relying solely on true causes can robustly model the mapping from states to optimal/expert actions under distributional shift.

In Appendix B, we prove that under mild assumptions, correctly modeling interventional queries does indeed require learning the correct causal graph $G$. In the car example, “setting” the brake light to on or off and observing the expert’s actions would yield a clear signal unobstructed by confounders: the brake light does not affect the expert’s braking behavior.

2 Causal Misidentification in Policy Learning Benchmarks and Realistic Settings

Before discussing our solution, we first present several testbeds and real-world cases where causal misidentification adversely influences imitation learning performance.

Control Benchmarks. We show that causal misidentification is induced with small changes to widely studied benchmark control tasks, simply by adding more information to the state, which intuitively ought to make the tasks easier, not harder. In particular, we add information about the previous action, which tends to correlate with the current action in the expert data for many standard control problems. This is a proxy for scenarios like our car example, in which correlates of past actions are observable in the state, and is similar to what we might see from other sources of knowledge about the past, such as memory or recurrence. We study three kinds of tasks: (i) MountainCar (continuous states, discrete actions), (ii) MuJoCo Hopper (continuous states and actions), (iii) Atari games: Pong, Enduro and UpNDown (states: two stacked consecutive frames, discrete actions).

For each task, we study imitation learning in two scenarios. In scenario A (henceforth called "confounded"), the policy sees the augmented observation vector, including the previous action. In the case of low-dimensional observations, the state vector is expanded to include the previous action at an index that is unknown to the learner. In the case of image observations, we overlay a symbol corresponding to the previous action at an unknown location on the image (see Fig 3). In scenario B ("original"), the previous action variable is replaced with random noise for low-dimensional observations. For image observations, the original images are left unchanged. Demonstrations are generated synthetically as described in Appendix A. In all cases, we use neural networks with identical architectures to represent the policies, and we train them on the same demonstrations.

Fig 4 shows the rewards against varying demonstration dataset sizes for MountainCar, Hopper, and Pong. Appendix E shows additional results, including for Enduro and UpNDown. All policies are trained to near-zero validation error on held-out expert state-action tuples. original produces rewards tending towards expert performance as the size of the imitation dataset increases. confounded either requires many more demonstrations to reach equivalent performance, or fails completely to do so.

Overall, the results are clear: across these tasks, access to more information leads to inferior performance. As Fig 11 in the appendix shows, this difference is not due to different training/validation losses on the expert demonstrations—for example, in Pong, confounded produces lower validation loss than original on held-out demonstration samples, but produces lower rewards when actually used for control. These results not only validate the existence of causal misidentification, but also provides us with testbeds for investigating a potential solution.

Real-World Driving. Our testbeds introduce deliberate nuisance variables to the “original” observation variables for ease of evaluation, but evidence suggests that misattribution is pervasive in common real-world imitation learning settings. Real-world problems often have no privileged “original” observation space, and very natural-seeming state spaces may still include nuisance factors—as in our dashboard light setting (Fig 1), where causal misattribution occurs when using the full image from the camera.

In particular, history would seem a natural part of the state space for real-world driving, yet recurrent/history-based imitation has been consistently observed in prior work to hurt performance, thus exhibiting clear symptoms of causal misidentification . While these histories contain valuable information for driving, they also naturally introduce information about nuisance factors such as previous actions. In all three cases, more information led to worse results for the behavioral cloning policy, but this was neither attributed specifically to causal misidentification, nor tackled using causally motivated approaches.

We draw the reader’s attention to particularly telling results from Wang et al. 2019 for learning to drive in near-photorealistic GTA-V environments, using behavior cloning with DAgger-inspired expert perturbation. Imitation learning policies are trained using overhead image observations with and without “history” information (history and no-history) about the ego-position trajectory of the car in the past.

Similar to our tests above, architectures are identical for the two methods. And once again, like in our tests above, history has better performance on held-out demonstration data, but much worse performance when actually deployed. Tab 1 shows these results, reproduced from Wang et al. 2019 Table II. These results constitute strong evidence for the prevalence of causal misidentification in realistic imitation learning settings. Bansal et al. 2019 also observe similar symptoms in a driving setting, and present a dropout approach to tackle it, which we compare to in our experiments. Subsequent to an earlier version of this work, Codevilla et al. 2019 also verify causal confusion in realistic driving settings, and propose measures to address a specific instance of causal confusion.

Resolving Causal Misidentification

Recall from Sec 3.1 that robustness to causal misidentification can be achieved by finding the true causal model of the expert’s actions. We propose a simple pipeline to do this. First, we jointly learn policies corresponding to various causal graphs (Sec 4.1). Then, we perform targeted interventions to efficiently search over the hypothesis set for the correct causal model (Sec 4.2).

In this step, we learn a policy corresponding to each candidate causal graph. Recall from Sec 3 that the expert’s actions $A$ are based on an unknown subset of the state variables $\{X_{i}\}_{i=1}^{n}$. Each $X_{i}$ may either be a cause or not, so there are $2^{n}$ possible graphs. We parameterize the structure $G$ of the causal graph as a vector of $n$ binary variables, each indicating the presence of an arrow from $X_{k}$ to $A$ in Fig 2. We then train a single graph-parameterized policy $\pi_{G}(X)=f_{\phi}([X\odot G,G])$, where $\odot$ is element-wise multiplication, and $[\cdot,\cdot]$ denotes concatenation. $\phi$ are neural network parameters, trained through gradient descent to minimize:

In Appendix D, we propose an approach to perform variational Bayesian causal discovery over graphs $G$, using a latent variable model to infer a distribution over functional causal models (graphs and associated parameters)—the modes of this distribution are the FCMs most consistent with the demonstration data. This resembles the scheme above, except that instead of uniform sampling, graphs are sampled preferentially from FCMs that fit the training demonstrations well. We compare both approaches in Sec 5, finding that simple uniform sampling nearly always suffices in preparation for the next step: targeted intervention.

2 Targeted Intervention

Having learned the graph-parameterized policy as in Sec 4.1, we propose targeted intervention to compute the likelihood $\mathcal{L}(G)$ of each causal graph structure hypothesis $G$. In a sense, imitation learning provides an ideal setting for studying interventional causal learning: causal misidentification presents a clear challenge, while the fact that the problem is situated in a sequential decision process where the agent can interact with the world provides a natural mechanism for carrying out limited interventions.

We propose two intervention modes, both of which can be carried out by interaction with the environment via the actions:

Expert query mode. This is the standard intervention approach applied to imitation learning: intervene on $X^{t}$ to assign it a value, and observe the expert response $A$. To do this, we sample a graph $G$ at the beginning of each intervention episode and execute the policy $\pi_{G}$. Once data is collected in this manner, we elicit expert labels on interesting states. This requires an interactive expert, as in DAgger , but requires substantially fewer expert queries than DAgger, because: (i) the queries serve only to disambiguate among a relatively small set of valid FCMs, and (ii) we use disagreement among the mixture of policies in $f_{\phi}$ to query the expert efficiently in an active learning approach. We summarize this approach in Algorithm 1.

Policy execution mode. It is not always possible to query an expert. For example, for a learner learning to drive a car by watching a human driver, it may not be possible to put the human driver into dangerous scenarios that the learner might encounter at intermediate stages of training. In cases like these where we would like to learn from pre-recorded demonstrations alone, we propose to intervene indirectly by using environmental returns (sum of rewards over time in an episode) $R=\sum_{t}r_{t}$. The policies $\pi_{G}(\cdot)=f_{\phi}([\cdot\odot G,G])$ corresponding to different hypotheses $G$ are executed in the environment and the returns $R_{G}$ collected. The likelihood of each graph is proportional to the exponentiated returns $\exp R_{G}$. The intuition is simple: environmental returns contain information about optimal expert policies even when experts are not queryable. Note that we do not even assume access to per-timestep rewards as in standard reinforcement learning; just the sum of rewards for each completed run. As such, this intervention mode is much more flexible. See Algorithm 2.

Note that both of the above intervention approaches evaluate individual hypotheses in isolation, but the number of hypotheses grows exponentially in the number of state variables. To handle larger states, we infer a graph distribution $p(G)$, by assuming an energy based model with a linear energy $E(G)=\langle w,G\rangle+b$, so the graph distribution is $p(G)=\prod_{i}p(G_{i})=\prod_{i}\text{Bernoulli}(G_{i}|\sigma(w_{i}/\tau))$, where $\sigma$ is the sigmoid, which factorizes in independent factors. The independence assumption is sensible as our approach collapses $p(G)$ to its mode before returning it and the collapsed distribution is always independent. $E(G)$ is inferred from linear regression on the likelihoods. This process is depicted in Algorithms 1 and 2. The above method can be formalized within the reinforcement learning framework . As we show in Appendix H, the energy-based model can be seen as an instance of soft Q-learning .

3 Disentangling Observations

In the above, we have assumed access to disentangled observations $X^{t}$. When this is not the case, such as with image observations, $X^{t}$ must be set to a disentangled representation of the observation at time $t$. We construct such a representation by training a $\beta$-VAE to reconstruct the original observations. To capture states beyond those encountered by the expert, we train with a mix of expert and random trajectory states. Once trained, $X^{t}$ is set to be the mean of the latent distribution produced at the output of the encoder. The VAE training objective encourages disentangled dimensions in the latent space . We employ CoordConv in both the encoder and the decoder architectures.

Experiments

We now evaluate the solution described in Sec 4 on the five tasks (MountainCar, Hopper, and 3 Atari games) described in Sec 3.2. In particular, recall that confounded performed significantly worse than original across all tasks. In our experiments, we seek to answer the following questions: (1) Does our targeted intervention-based solution to causal misidentification bridge the gap between confounded and original? (2) How quickly does performance improve with intervention? (3) Do both intervention modes (expert query, policy execution) described in Sec 4.2 resolve causal misidentification? (4) Does our approach in fact recover the true causal graph? (5) Are disentangled state representations necessary?

In each of the two intervention modes, we compare two variants of our method: unif-intervention and disc-intervention. They only differ in the training of the graph-parameterized mixture-of-policies $f_{\phi}$—while unif-intervention samples causal graphs uniformly, disc-intervention uses the variational causal discovery approach mentioned in Sec 4.1, and described in detail in Appendix D.

Baselines. We compare our method against three baselines applied to the confounded state. dropout trains the policy using Eq 1 and evaluates with the graph $G$ containing all ones, which amounts to dropout regularization during training, as proposed by Bansal et al. 2019. dagger addresses distributional shift by querying the expert on states encountered by the imitator, requiring an interactive expert. We compare dagger to our expert query intervention approach. Lastly, we compare to Generative Adversarial Imitation Learning (gail) . gail is an alternative to standard behavioral cloning that works by matching demonstration trajectories to those generated by the imitator during roll-outs in the environment. Note that the PC algorithm , commonly used in causal discovery from passive observational data, relies on the faithfulness assumption, which causes it to be infeasible in our setting, as explained in Appendix C. See Appendices B & D for details.

Intervention by policy execution. Fig 7 plots episode rewards versus number of policy execution intervention episodes for MountainCar and Hopper. The reward always corresponds to the current mode $\argmax_{G}p(G)$ of the posterior distribution over graphs, updated after each episode, as described in Algorithm 2. In these cases, both unif-intervention and disc-intervention eventually converge to models yielding similar rewards, which we verified to be the correct causal model i.e., true causes are selected and nuisance correlates left out. In early episodes on MountainCar, disc-intervention benefits from the prior over graphs inferred in the variational causal discovery phase. However, in Hopper, the simpler unif-intervention performs just as well. dropout does indeed help in both settings, as reported in Bansal et al. 2019, but is significantly poorer than our approach variants. gail requires about 1.5k episodes on Hopper to match the performance of our approaches, which only need tens of episodes. Appendix G further analyzes the performance of gail. Standard implementations of gail do not handle discrete action spaces, so we do not evaluate it on MountainCar.

As described in Sec 4.3, we use a VAE to disentangle image states in Atari games to produce 30-D representations for Pong and Enduro and 50-D representations for UpNDown. We set this dimensionality heuristically to be as small as possible, while still producing good reconstructions as assessed visually. Requiring the policy to utilize the VAE representation without end-to-end training does result in some drop in performance, as seen in Fig 6. However, causal misidentification still causes a very large drop of performance even relative to the baseline VAE performance. disc-intervention is hard to train as the cardinality of the state increases, and yields only minor advantages on Hopper (14-D states), so we omit it for these Atari experiments. As Fig 6 shows, unif-intervention indeed improves significantly over confounded w/ vae in all three cases, matching original w/ vae on Pong and UpNDown, while the dropout baseline only improves UpNDown. In our experiments thus far, gail fails to converge to above-chance performance on any of the Atari environments. These results show that our method successfully alleviates causal misidentification within relatively few trials.

Intervention by expert queries. Next, we perform direct intervention by querying the expert on samples from trajectories produced by the different causal graphs. In this setting, we can also directly compare to dagger . Fig 8 shows results on MountainCar and Hopper. Both our approaches successfully improve over confounded within a small number of queries. Consistent with policy execution intervention results reported above, we verify that our approach again identifies the true causal model correctly in both tasks, and also performs better than dropout in both settings. It also exceeds the rewards achieved by dagger, while using far fewer expert queries. In Appendix F, we show that dagger requires hundreds of queries to achieve similar rewards for MountainCar and tens of thousands for Hopper. Finally, gail with 1.5k episodes outperforms our expert query interventions approach. Recall however from Fig 8 that this is an order of magnitude more than the number of episodes required by our policy intervention approach.

Once again, disc-intervention only helps in early interventions on MountainCar, and not at all on Hopper. Thus, our method’s performance is primarily attributable to the targeted intervention stage, and the exact choice of approach used to learn the mixture of policies is relatively insignificant.

Overall, of the two intervention approaches, policy execution converges to better final rewards. Indeed, for the Atari environments, we observed that expert query interventions proved ineffective. We believe this is because expert agreement is an imperfect proxy for true environmental rewards.

Interpreting the learned causal graph. Our method labels each dimension of the VAE encoding of the frame as a cause or nuisance variable. In Fig 9, we analyze these inferences in the Pong environment as follows: in the top row, a frame is encoded into the VAE latent, then for all nuisance dimensions (as inferred by our approach unif-intervention), that dimension is replaced with a sample from the prior, and new samples are generated. In the bottom row, the same procedure is applied with a random graph that has as many nuisance variables as the inferred graph. We observe that in the top row, the causal variables (the ball and paddles) are shared between the samples, while the nuisance variables (the digit) differ, being replaced either with random digits or unreadable digits. In the bottom row, the causal variables differ strongly, indicating that important aspects of the state are judged as nuisance variables. This validates that, consistent with MountainCar and Hopper, our approach does indeed identify true causes in Pong.

Necessity of disentanglement. Our intervention method assumes a disentangled representation of state. Otherwise, each of the $n$ individual dimensions in the state might capture both causes as well as nuisance variables and the problem of discovering true causes is no longer reducible to searching over $2^{n}$ graphs.

To test this empirically, we create a variant of our MountainCar confounded testbed, where the 3-D past action-augmented state vector is rotated by a fixed, random rotation. After training the graph-conditioned policies on the entangled and disentangled confounded state, and applying 30 episodes of policy execution intervention or 20 expert queries, we get the results shown in Tab 2. The results are significantly lower in the entangled than in the disentangled (non-rotated) setting, indicating disentanglement is important for the effectiveness of our approach.

Conclusions

We have identified a naturally occurring and fundamental problem in imitation learning, “causal misidentification”, and proposed a causally motivated approach for resolving it. While we observe evidence for causal misidentification arising in natural imitation learning settings, we have thus far validated our solution in somewhat simpler synthetic settings intended to mimic them. Extending our solution to work for such realistic scenarios is an exciting direction for future work. Finally, apart from imitation, general machine learning systems deployed in the real world also encounter “feedback” , which opens the door to causal misidentification. We hope to address these more general settings in the future.

We would like to thank Karthikeyan Shanmugam and Shane Gu for pointers to prior work early in the project, and Yang Gao, Abhishek Gupta, Marvin Zhang, Alyosha Efros, and Roberto Calandra for helpful discussions in various stages of the project. We are also grateful to Drew Bagnell and Katerina Fragkiadaki for helpful feedback on an earlier draft of this paper. This project was supported in part by Berkeley DeepDrive, NVIDIA, and Google.

References

Appendix A Expert Demonstrations

To collect demonstrations, we first train an expert with reinforcement learning. We use DQN for MountainCar, TRPO for Hopper, and PPO for the Atari environments (Pong, UpNDown, Enduro). This expert policy is executed in the environment to collect demonstrations.

Appendix B Necessity of Correct Causal Model

Faithfulness: A causal model is said to be faithful when all conditional independence relationships in the distribution are represented in the graph.

Let the expert’s functional causal model be $(G^{*},\theta_{G^{*}}^{*})$, with causal graph $G^{*}\in\mathcal{G}$ as in Figure 2 and function parameters $\theta_{G^{*}}^{*}$. We assume some faithful learner $(\hat{G},\theta_{\hat{G}}),\hat{G}\in\mathcal{G}$ that agrees on the interventional query:

For graph $G$, define the index set of state variables that are independent of the action in the mutilated graph $G_{\bar{X}}$:

From the assumption of matching interventional queries and the assumption of faithfulness, it follows that: $I_{G^{*}}=I_{\hat{G}}$. From the graph, we observe that $I_{G}=\{i|(X_{i}\to A)\not\in G\}$ and thus $G^{*}=\hat{G}$. ∎

Appendix C Passive Causal Discovery, Faithfulness and Determinism

In many learning scenarios, much information about the causal model can already be inferred passively from the data. This is the problem of causal discovery. Ideally, it would allow us to perform statistical analysis on the random variables in Fig 2 in the demonstration data to determine whether variable $X^{t}_{i}$ is a cause of the next expert action $A^{t}$ or a nuisance variable.

Causal discovery algorithms, such as the PC algorithm test a series of conditional independence relationships in the observed data and construct the set of possible causal graphs whose conditional independence relationships match the data. It does so by assuming faithfulness, meaning the joint probability of random variables contains no more conditional independence relationships than the causal graph. In the particular case of the causal model in Fig 2, it is easy to see that $X^{t}_{i}$ is a cause of $A^{t}$, and thus that the arrow $X^{t}_{i}\to A^{t}$ exists, if and only if X^{t}_{i}\not\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}A^{t}|Z^{t}, meaning that $X^{t}_{i}$ provides extra information about $A^{t}$ if $Z^{t}$ is already known.

We test this procedure empirically by evaluating the mutual information $I(X^{t}_{i};A^{t}|Z^{t})$ for the confounded MountainCar benchmark, using the estimator from Gao et al. 2017. The results in Table 3 show that all state variables are correlated with the expert’s action, but that all become mostly independent given the confounder $Z^{t}$, implying none are causes.

Passive causal discovery failed because the critical faithfulness assumption is violated in the MountainCar case. Whenever a state variable $X^{t}_{i}$ is a deterministic function of the past $Z^{t}$, so that X^{t}_{i}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}A^{t}|Z^{t} always holds and a passive discovery algorithm concludes no arrow $X^{t}_{i}\to A^{t}$ exists. Such a deterministic transition function for at least a part of the state is very common in realistic imitation learning scenarios, making passive causal discovery inapplicable. Active interventions must thus be used to determine the causal model.

Appendix D Variational Causal Discovery

The problem of discovering causal graphs from passively observed data is called causal discovery. The PC algorithm is arguably the most widely used and easily implementable causal discovery algorithm. In the case of Fig 2, the PC algorithm would imply the absence of the arrow $X^{t}_{i}\rightarrow A^{t}$, if the conditional independence relation A^{t}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X^{t}_{i}|Z^{t} holds, which can be tested by measuring the mutual information. However, the PC algorithm relies on faithfulness of the causal graph. That is, conditional independence must imply d-separation in the graph. However, faithfulness is easily violated in a Markov decision process. If for some $i$, $X^{t}_{i}$ is a cause of the expert’s action $A^{t}$ (the arrow $X^{t}_{i}\rightarrow A^{t}$ should exist), but $X^{t}_{i}$ is the result of a deterministic function of $Z^{t}$, then always A^{t}\mathchoice{\mathrel{\hbox to0.0pt{\displaystyle\perp\hss}\mkern 2.0mu{\displaystyle\perp}}}{\mathrel{\hbox to0.0pt{\textstyle\perp\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptstyle\perp\hss}\mkern 2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox to0.0pt{\scriptscriptstyle\perp\hss}\mkern 2.0mu{\scriptscriptstyle\perp}}}X^{t}_{i}|Z^{t} and the PC algorithm would wrongly conclude that the arrow $X^{t}_{i}\rightarrow A^{t}$ is absent. More generally, faithfulness places strong constraints on the expert graph. For example, a visual state may contain unchanging elements such as the car frame in Fig 1, which are by definition deterministic functions of the past. As another example, goal-conditioned tasks must include a constant goal in the state variable at each time, which once again has deterministic transitions, violating faithfulness.

We take a Bayesian approach to causal discovery from demonstrations. Recall from Sec 3 that the expert’s actions $A$ are based on an unknown subset of the state variables $\{X_{i}\}_{i=1}^{n}$. Each $X_{i}$ may either be a cause or not, so there are $2^{n}$ possible graphs. We now define a variational inference approach to infer a distribution over functional causal models (graphs and associated parameters) such that its modes are consistent with the demonstration data $D$.

While Bayesian inference is intractable, variational inference can be used to find a distribution that is close to the true posterior distribution over models. We parameterize the structure $G$ of the causal graph as a vector of $n$ correlated Bernoulli random variables $G_{k}$, each indicating the presence of a causal arrow from $X_{k}$ to $A$. We assume a variational family with a point estimate $\theta_{G}$ of the parameters corresponding to graph $G$ and use a latent variable model to describe the correlated Bernoulli variables, with a standard normal distribution $q(U)$ over latent random variable $U$:

We now optimise the evidence lower bound (ELBO):

$\pi(A_{i}|X_{i},G,\theta_{G})$ is the likelihood of the observations $X$ under the FCM $(G,\theta_{G})$. It is modelled by a single neural network $f_{\phi}([X\odot G,G])$, where $\odot$ is the element-wise multiplication, $[\cdot,\cdot]$ denotes concatenation and $\phi$ are neural network parameters.

Entropy

The entropy term of the KL divergence, $\mathcal{H}_{q}$, acts as a regularizer to prevent the graph distribution from collapsing to the maximum a-posteriori estimate. It is intractable to directly maximize entropy, but a tractable variational lower bound can be formulated. Using the product rule of entropies, we may write:

Prior

The prior $p(G)$ over graph structures is set to prefer graphs with fewer causes for action $A$—it is thus a sparsity prior:

Optimization

Note that $G$ is a discrete variable, so we cannot use the reparameterization trick . Instead, we use the Gumbel Softmax trick to compute gradients for training $q_{\psi}(G_{k}|U)$. Note that this does not affect $f_{\phi}$, which can be trained with standard backpropagation.

The loss of Eq 3 is easily interpretable independent of the formalism of variational Bayesian causal discovery. A mixture of predictors $f_{\phi}$ is jointly trained, each paying attention to diverse sparse subsets (identified by $G$) of the inputs. This is related to variational dropout . Once this model is trained, $q_{\psi}(G)$ represents the hypothesis distribution over graphs, and $\pi_{G}(x)=f_{\phi}([x\odot G,G])$ represents the imitation policy corresponding to a graph $G$. Fig 10 shows the architecture.

Usage for Targeted Interventions

In our experiments, we also evaluate the usefulness of causal discovery process to set a prior for the targeted interventions described in Sec 4.2. In Algorithm 1 and 2, we implement this by initializing $p(G)$ to the discovered distribution (rather than uniform).

Appendix E Additional Results: Diagnosing Causal Misidentification

In Fig 11 we show the causal misidentification in several environments. We observe that while training and validation losses for behavior cloning are frequently near-zero for both the original and confounded policy, the confounded policy consistently yields significantly lower reward when deployed in the environment. This confirms the causal misidentification problem.

Appendix F DAgger with many more interventions

In the main paper, we showed that DAgger performed poorly with equl number of expert interventions as our method. How many more samples does it need to do well?

The results in Fig 12 show that DAgger requires hundreds of samples before reaching rewards comparable to the rewards achieved by a non-DAgger imitator trained on the original state.

Appendix G GAIL Training Curves

In Figure 13 we show the average training curves of GAIL on the original and confounded state. Error bars are 2 standard errors of the mean. The confounded and original training curve do not differ significantly, indicating that causal confusion is not an issue with GAIL. However, training requires many interactions with the environment.

Appendix H Intervention Posterior Inference as Reinforcement Learning

Given a method of evaluating the likelihood $p(\mathcal{O}|G)$ of a certain graph $G$ to be optimal and a prior $p_{0}(G)$, we wish to infer the posterior $p(G|\mathcal{O})$. The number of graphs is finite, so we can compute this posterior exactly. However, there may be very many graphs, so that impractically many likelihood evaluations are necessary. Only noisy samples from the likelihood can be obtained, as in the case of intervention through policy execution, where the reward is noisy, this problem is exacerbated.

If on the other hand, a certain structure on the policy is assumed, the sample efficiently can be drastically improved, even though policy can no longer be exactly inferred. This can be done in the framework of Variational Inference. For a certain variational family, we wish to find, for some temperature $\tau$:

The variational family we assume is the family of independent distributions: