Sequential Causal Imitation Learning with Unobserved Confounders

Introduction

Without access to observational data, an agent must learn how to operate at a suitable level of performance through trial and error . This from-scratch approach is often impractical in environments with the potential of extreme negative - and final - outcomes (driving off a cliff). While both Nature and machine learning researchers have approached the problem from a wide variety of perspectives, a particularly potent method which has been used with great success in many learning machines, including humans, is exploiting observations of other agents in the environment .

Learning to act by observing other agents offers a data multiplier, allowing agents to take into account others’ experiences. Even when the precise loss function is unknown (what exactly goes into being a good driver?), the agent can attempt to learn from “experts”, namely agents which are known to gain an acceptable reward at the target task. This approach has been studied under the umbrella of imitation learning . Several methods have been proposed, including inverse reinforcement learning and behavior cloning . The former attempts to reconstruct the loss/reward function that the experts minimize and then use it for optimization; the latter directly copies the expert’s actions (behavior cloning).

Despite the power entailed by this approach, it relies on a somewhat stringent condition: the expert and imitator’s sensory capabilities need to be perfectly matched. As an example, self-driving cars rely solely on cameras or lidar, completely ignoring the auditory dimension - and yet most human demonstrators are able to exploit this data, especially in dangerous situations (car horns, screeching tires). Perhaps without a microphone, the self-driving car would incorrectly attribute certain behaviors to visual stimuli, leading to a poor policy? For concreteness, consider the scenario shown in Fig. 1(a), where the human driver ($X$, i.e., the demonstrator, in blue) is looking forward ($F$), and can hear car horns ($H$) from cars behind ($B$), and to the side ($S$). The driver’s performance is represented by a variable $Y$ (red), which is unobserved (dashed node). Since our dataset only contains visual data, car horns $H$ remain unobserved to the learning agent (i.e., the imitator). Despite not being able to hear car horns, the learner from Figure 1(a) had a full view of the car’s surroundings, including cars behind and to the side, which turns out to be sufficient to perform imitation in this example. Consider an instance where $F,B,S$ are drawn uniformly over $\{0,1\}$. The reward $Y$ is decided by $\neg X\oplus F\oplus B\oplus S$; $\oplus$ represents the exclusive-or operator. The human driver decides the action $X\leftarrow H$ where values of horn $H$ is given by $F\oplus B\oplus S$. Preliminary analysis reveals that the learner could perfectly mimic the demonstrator’s decision-making process using an imitating policy $X\leftarrow F\oplus B\oplus S$. On the other hand, if the driving system does not have side cameras, the side view $S$ becomes latent; see Figure 1(b). The learner’s reward ${\rm I\kern-3.00003ptE}[Y|\text{do}(\pi)]$ is equal to $0.5$ for any policy $\pi(x|f,b)$, which is far from the optimal demonstrator’s performance, ${\rm I\kern-3.00003ptE}[Y]=1$.

Based on these examples, there arises the question of determining precise conditions under which an agent can account for the lack of knowledge or observations available to the expert, and how this knowledge should be combined to generate an optimal imitating policy, giving identical performance as the expert on measure $Y$. These questions have been recently investigated in the context of causal imitation learning , where a complete graphical condition and algorithm were developed for determining imitability in the single-stage decision-making setting with partially observable models (i.e., in non-Markovian settings). Other structural assumptions, such as linearity , were also explored in the literature, but were still limited to a single action. Finally, explore the case when expert and imitator can observe the same contexts, but the causal diagram is not available. Despite this progress, it is still unclear how to systematically imitate, or even whether imitation is possible when a learner must make several actions in sequence, where expert and imitator observe differing sets of variables (e.g., Figures 1(c) and 1(d)).

The goal of this paper is to fill this gap in understanding. More specifically, our contributions are as follows. (1) We provide a graphical criterion for determining whether imitability is feasible in sequential settings based on a causal graph encoding the domain’s causal structure. (2) We propose an efficient algorithm to determine imitability and to find the policy for each action that leads to proper imitation. (3) We prove that the proposed criterion is complete (i.e. both necessary and sufficient). Finally, we verify that our approach compares favorably with existing methods in contexts where a demonstrator has access to latent variables through simulations. Due to space constraints, proofs are provided in the complete technical report .

We start by introducing the notation and definitions used throughout the paper. In particular, we use capital letters for random variables ($Z$), and small letters for their values ($z$). Bolded letters represent sets of random variables and their samples ($\bm{Z}=\{Z_{1},...,Z_{n}\}$, $\bm{z}=\{z_{1}\sim Z_{1},...,z_{n}\sim Z_{n}\}$). $|\bm{Z}|$ represents a set’s cardinality. The joint distribution over variables $\bm{Z}$ is denoted by $P(\bm{Z})$. To simplify notation, we consistently use the shorthand $P(z_{i})$ to represent probabilities $P(Z_{i}=z_{i})$.

The basic semantic framework of our analysis rests on structural causal models (SCMs) [17, Ch. 7]. An SCM $M$ is a tuple $\langle\bm{U},\bm{V},\bm{F},P(\bm{u})\rangle$ with $\bm{V}$ the set of endogenous, and $\bm{U}$ exogenous variables. $\bm{F}$ is a set of structural functions s.t. for $f_{V}\in\bm{F}$, $V\leftarrow f_{V}(\mathit{pa}_{V},u_{V})$, with $\mathit{PA}_{V}\subseteq\bm{V},U_{V}\subseteq\bm{U}$ . Values of $\bm{U}$ are drawn from an exogenous distribution $P(\bm{u})$, inducing distribution $P(\bm{V})$ over the endogenous $\bm{V}$. Since the learner can observe only a subset of endogenous variables, we split $\bm{V}$ into $\bm{O}\subseteq\bm{V}$ (observed) and $\bm{L}=\bm{V}\setminus\bm{O}$ (latent) sets of variables. The marginal $P(\bm{O})$ is thus referred to as the observational distribution.

Each SCM $M$ is associated with a causal diagram $\mathcal{G}$ where (e.g., see Figure 2(d)) solid nodes represent observed variables $\bm{O}$, dashed nodes represent latent variables $\bm{L}$, and arrows represent the arguments $\mathit{pa}(V)$ of each functional relationship $f_{V}$. Exogenous variables $\bm{U}$ are not explicitly shown; a bi-directed arrow between nodes $V_{i}$ and $V_{j}$ indicates the presence of an unobserved confounder (UC) affecting both $V_{i}$ and $V_{j}$. We will use standard conventions to represent graphical relationships such as parents, children, descendants, and ancestors. For example, the set of parent nodes of $\bm{X}$ in $\mathcal{G}$ is denoted by $\mathit{pa}(\bm{X})_{\mathcal{G}}=\cup_{X\in\bm{X}}\mathit{pa}(X)_{\mathcal{G}}$. $\mathit{ch}$, $\mathit{de}$ and $\mathit{an}$ are similarly defined. Capitalized versions $\mathit{Pa},\mathit{Ch},\mathit{De},\mathit{An}$ include the argument as well, e.g. $\mathit{De}(\bm{X})_{\mathcal{G}}=\mathit{de}(\bm{X})_{\mathcal{G}}\cup\bm{X}$. An observed variable $V_{i}\in\bm{O}$ is an effective parent of $V_{j}\in\bm{V}$ if there is a directed path from $V_{i}$ to $V_{j}$ in $\mathcal{G}$ such that every internal node on the path is in $\bm{L}$. We define $\mathit{pa}^{+}(\bm{S})$ as the set of effective parents of variables in $\bm{S}$, excluding $\bm{S}$ itself, and $\mathit{Pa}^{+}(\bm{S})$ as $\bm{S}\cup\mathit{pa}^{+}(\bm{S})$. Other relations, like $ch^{+}(\bm{S})$ are defined similarly.

A path from a node $X$ to a node $Y$ in $\mathcal{G}$ is said to be “active" conditioned on a (possibly empty) set $\bm{W}$ if there is a collider at $A$ along the path ($\rightarrow A\leftarrow$) only if $A\in\mathit{An}(\bm{W})$, and the path does not otherwise contain vertices from $\bm{W}$ (d-separation, ). $\bm{X}$ and $\bm{Y}$ are independent conditioned on $\bm{W}$ $(\bm{X}\perp\!\!\!\perp\bm{Y}|\bm{W})_{\mathcal{G}}$ if there are no active paths between any $X\in\bm{X}$ and $Y\in\bm{Y}$. For a subset $\bm{X}\subseteq\bm{V}$, the subgraph obtained from $\mathcal{G}$ with edges outgoing from $\bm{X}$ / incoming into $\bm{X}$ removed is written $\mathcal{G}_{\underline{\bm{X}}}$/$\mathcal{G}_{\overline{\bm{X}}}$ respectively. Finally, we utilize a grouping of observed nodes, called confounded components (c-components, ).

For a causal diagram $\mathcal{G}$, let $\bm{N}$ be a set of unobserved variables in $\bm{L}\cup\bm{U}$. A set $\bm{C}\subseteq\mathit{Ch}(\bm{N})\cap\bm{O}$ is a c-component if for any pair $U_{i},U_{j}\in\bm{N}$, there exists a path between $U_{i}$ and $U_{j}$ in $\mathcal{G}$ such that every observed node $V_{k}\in\bm{O}$ on the path is a collider (i.e., $\rightarrow V_{k}\leftarrow$).

C-components correspond to observed variables whose values are affected by related sets of unobserved common causes, such that if $A,B\in\bm{C}$, $(A\not\perp\!\!\!\perp B|\bm{O}\setminus\{A,B\})$. In particular, we focus on maximal c-components $\bm{C}$ , where there doesn’t exist c-component $\bm{C}^{\prime}$ s.t. $\bm{C}\subset\bm{C}^{\prime}$. The collection of maximal c-components forms a partition $\bm{C}_{1},\dots,\bm{C}_{m}$ over observed variables $\bm{O}$. For any set $S\subseteq\bm{O}$, let $\bm{C}(S)$ be the union of c-components $\bm{C}_{i}$ that contain variables in $S$. For instance, for variable $Z$ in Figure 1(d), the c-component $\bm{C}(\{Z\})=\{Z,X_{1}\}$.

Causal Sequential Imitation Learning

We are interested in learning a policy over a series of actions $\bm{X}\subseteq\bm{O}$ so that an imitator gets average reward $Y\in\bm{V}$ identical to that of an expert demonstrator. More specifically, let variables in $\bm{X}$ be ordered by $X_{1},\dots,X_{n}$, $n=|\bm{X}|$. Actions are taken sequentially by the imitator, where only information available at the time of the action can be used to inform a policy for $X_{i}\in\bm{X}$. To encode the ordering of observations and actions in time, we fix a topological ordering on the variables of $\mathcal{G}$, which we call the “temporal ordering”. We define functions $\before(X_{i})$ and $\after(X_{i})$ to represent nodes that come before/after an action $X_{i}\in\bm{X}$ following the ordering, excluding $X_{i}$ itself. A policy $\pi$ on actions $\bm{X}$ is a sequence of decision rules $\{\pi_{1},\dots,\pi_{n}\}$ where each $\pi_{i}(X_{i}|\bm{Z}_{i})$ is a function mapping from domains of covariates $\bm{Z}_{i}\subseteq\before(X_{i})$ to the domain of action $X_{i}$. The imitator following a policy $\pi$ replacing the demonstrator in an environment is encoded by replacing the expert’s original policy in the SCM $M$ with $\pi$, which gives the results of the imitator’s actions as $P(\bm{V}|\text{do}(\pi))$. Our goal is to learn an imitating policy $\pi$ such that the induced distribution $P(Y|\text{do}(\pi))$ perfectly matches the original expert’s performance $P(Y)$. Formally

Given a causal diagram $\mathcal{G}$, $\bm{Y}\subseteq\bm{V}$ is said to be imitable with respect to actions $\bm{X}\subseteq\bm{O}$ in $\mathcal{G}$ if there exists $\pi\in\Pi$ uniquely discernible from the observational distribution $P(\bm{O})$ such that for all possible SCMs $M$ compatible with $\mathcal{G}$, $P(\bm{Y})_{M}=P(\bm{Y}|do(\pi))_{M}$.

In other words, the expert’s performance on reward $Y$ is imitable if any set of SCMs must share the same imitating policy $\pi\in\Pi$ whenever they generate the same causal diagram $\mathcal{G}$ and the observational distribution $P(\bm{O})$. Henceforth, we will consistently refer to Definition 2.1 as the fundamental problem of causal imitation learning. For single stage decision-making problems ($\bm{X}=\{X\}$), demonstrated imitability for reward $Y$ if and only if there exists a set $\bm{Z}\subseteq\before(X)$ such that $\left(Y\perp\!\!\!\perp X|\bm{Z}\right)_{\mathcal{G}_{\underline{X}}}$, called the backdoor admissible set, [17, Def. 3.3.1] ($\bm{Z}=\{F,B,S\}$ in Figure 1(a)). It is verifiable that an imitating policy is given by $\pi(X|F,B,S)=P(X|F,B,S)$.

Since the backdoor criterion is complete for the single-stage problem, one may be tempted to surmise that a version of the criterion generalized to multiple interventions might likewise solve the imitability problem in the general case ($|\bm{X}|>1$). Next we show that this is not the case. Let $\bm{X}_{1:i}$ stand for a sequence of variables $\{X_{1},\dots,X_{i}\}$; $\bm{X}_{1:i}=\emptyset$ if $i<1$. generalized the backdoor criterion to the sequential decision-making setting as follows:

Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$, and target node $Y$, sets $\bm{Z}_{1}\subseteq\before(X_{1}),\dots,\bm{Z}_{n}\subseteq\before(X_{n})$ satisfy the sequential backdoor for $(\mathcal{G},\bm{X},Y)$ if for each $X_{i}\in\bm{X}$ such that $(Y\perp\!\!\!\perp X_{i}|\bm{X}_{1:i-1},\bm{Z}_{1:i})_{\mathcal{G}_{\underline{X}_{i}\overline{\bm{X}}_{i+1:n}}}$.

While the sequential backdoor is an extension of the backdoor to multi-stage decisions, its existence does not always guarantee the imitability of latent reward $Y$. As an example, consider the causal diagram $\mathcal{G}$ described in Figure 1(d). In this case, $\bm{Z}_{1}=\{\},\bm{Z}_{2}=\{Z\}$, $\{(X_{1},\bm{Z}_{1}),(X_{2},\bm{Z}_{2})\}$ is a sequential backdoor set for $(\mathcal{G},\{X_{1},X_{2}\},Y)$, but there are distributions for which no agent can imitate the demonstrator’s performance ($Y$) without knowledge of either the latent $U_{1}$ or $U_{2}$. To witness, suppose that the adversary sets up an SCM with binary variables as follows: $U_{1},U_{2}\sim Bern(0.5)$, with $X_{1}:=U_{1}$, $Z:=U_{1}\oplus U_{2}$, $X_{2}:=Z$ and $Y=\lnot(X_{1}\oplus X_{2}\oplus U_{2})$, with $\oplus$ as a binary XOR. The fact that $U\oplus U=0$ is exploited to generate a chain where each latent variable appears exactly twice in $Y$, making $Y=\lnot(U_{1}\oplus(U_{1}\oplus U_{2})\oplus U_{2})=1$. On the other hand, when imitating, $X_{1}$ can no longer base its value on $U_{1}$, making the imitated $\hat{Y}=\lnot(\hat{X}_{1}\oplus\hat{X}_{2}\oplus U_{2})$. The imitator can do no better than ${\rm I\kern-3.00003ptE}[\hat{Y}]=0.5$! We refer readers to [9, Proposition C.1] for a more detailed explanation.

We now introduce the main result of this paper: a generalized backdoor criterion that allows one to learn imitating policies in the sequential setting. For a sequence of covariate sets $\bm{Z}_{1}\subseteq\before(X_{1}),\dots,\bm{Z}_{n}\subseteq\before(X_{n})$, let $\mathcal{G}^{\prime}_{i}$, $i=1,\dots,n$, be the manipulated graph obtained from a causal diagram $\mathcal{G}$ by first (1) removing all arrows coming into nodes in $X_{i+1:n}$; and (2) adding arrows $\bm{Z}_{i+1}\rightarrow X_{i+1},\dots,\bm{Z}_{n}\rightarrow X_{n}$. We can then define a sequential backdoor criterion for causal imitation as follows:

Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$, and target node $Y$, sets $\bm{Z}_{1}\subseteq\before(X_{1}),\dots,\bm{Z}_{n}\subseteq\before(X_{n})$ satisfy the “sequential $\pi$-backdoor" The $\pi$ in “$\pi$-backdoor” is part of the name, and does not refer to any specific policy. for $(\mathcal{G},\bm{X},Y)$ if at each $X_{i}\in\bm{X}$, either (1) $(X_{i}\perp\!\!\!\perp Y|\bm{Z}_{i})$ in $(\mathcal{G}^{\prime}_{i})_{\underline{X_{i}}}$, or (2) $X_{i}\notin An(Y)$ in $\mathcal{G}^{\prime}_{i}$.

The first condition of Definition 2.3 is similar to the backdoor criterion where $\bm{Z}_{i}$ is a set of variables that effectively encodes all information relevant to imitating $X_{i}$ with respect to $Y$. In other words, if the joint $P(\bm{Z}_{i}\cup\{X_{i}\})$ matches when both expert and imitator are acting, then an adversarial $Y$ cannot distinguish between the two. The critical modification of the original $\pi$-backdoor for the sequential setting comes from the causal graph in which this check happens. $\mathcal{G}^{\prime}_{i}$ can be seen as $\mathcal{G}$ with all future actions of the imitator already encoded in the graph. That is, when performing a check for $X_{i}$, it is done with all actions after $i$ being performed by the imitator rather than expert, with the associated parents of each future $X_{j>i}$ replaced with their corresponding imitator’s conditioning set. Several examples of $\mathcal{G}^{\prime}_{i}$ are shown in Figure 3.

The second condition allows for the case where an action at $X_{i}$ has no effect on the value of $Y$ once future actions are taken. Since $\mathcal{G}^{\prime}_{i}$ has modified parents for future $\bm{X}_{j>i}$, the value of $X_{i}$ might no longer be relevant at all to $Y$, i.e. $Y$ would get the same input distribution no matter what policy is chosen for $X_{i}$. This allows $X_{i}$ to fail condition (1), meaning that it is not imitable by itself, but still be part of an imitable set $\bm{X}$, because future actions can shield $Y$ from errors made at $X_{i}$.

The distinction between condition 1 and condition 2 is shown in Figure 3(c): in the original graph $\mathcal{G}$ described in Figure 2(c), if $Z$ comes after $X_{1}$, then there is no valid adjustment set that can d-separate $X_{1}$ from $Y$. However, if the imitating policy for $X_{2}$ uses $Z$ instead of $W$ or $X_{1}$ (i.e. $\pi_{X_{2}}=P(X_{2}|Z)$), $X_{1}$ will no longer be an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$. In effect, the action made at $X_{2}$ ignores the inevitable mistakes made at $X_{1}$ due to not having access to confounder $U_{1}$ when taking the action.

Indeed, the sequential $\pi$-backdoor criterion can be seen as a recursively applying the single-action $\pi$-backdoor. Starting from the last action $X_{k}$ in temporal order, one can directly show that $Y$ is imitable using a backdoor admissible set $\bm{Z}_{k}$ (or $X_{k}$ doesn’t affect $Y$ by any causal path). Replacing $X_{k}$ in the SCM with this new imitating policy, the resulting SCM with graph $G^{\prime}_{k-1}$ has an identical distribution over $Y$ as $\mathcal{G}$. The procedure can then be repeated for $X_{k-1}$ using $G^{\prime}_{k-1}$ as the starting graph, and continued recursively, showing imitability for the full set:

Given a causal diagram $\mathcal{G}$, a set of action variables $\bm{X}$, and target node $Y$, if there exist sets $\bm{Z}_{1},\bm{Z}_{2},...,\bm{Z}_{k}$ that satisfy the sequential $\pi$-backdoor criterion with respect to $(\mathcal{G},\bm{X},Y)$, then $Y$ is imitable with respect to $\bm{X}$ in $\mathcal{G}$ with policy $\pi(X_{i}|\bm{Z_{i}})=P(X_{i}|\bm{Z}_{i})$ for each $X_{i}\in\bm{X}$.

Theorem 2.1 establishes the sufficiency of the sequential $\pi$-backdoor for imitation learning. Consider again the diagram in Figure 2(c). It is verifiable that covariate sets $\bm{Z}_{1}=\{\},\bm{Z}_{2}=\{Z\}$ are sequential $\pi$-backdoor admissible. Theorem 2.1 implies that the imitating policy is given by $\pi_{1}(X_{1})=P(X_{1})$ and $\pi_{2}(X_{2}|Z)=P(X_{2}|Z)$. Once $\pi$-backdoor admissible sets are obtained, the imitating policy can be learned from the observational data through standard density estimation methods for stochastic policies, and supervised learning methods for deterministic policies. This means that the sequential $\pi$-backdoor is a method for choosing a set of covariates to use when performing imitation learning, which can be used instead of $Pa(X_{i})$ for each $X_{i}\in\bm{X}$ in the case when the imitator does not observe certain elements of $Pa(\bm{X})$. With the covariates chosen using the sequential $\pi$-backdoor, one can use domain-specific algorithms for computing an imitating policy based on the observational data.

Finding Sequential π\pi-Backdoor Admissible Sets

At each $X_{i}$, the sequential $\pi$-backdoor criterion requires that $\bm{Z}_{i}$ is a back-door adjustment set in the manipulated graph $\mathcal{G}^{\prime}_{i}$. There already exist efficient methods for finding adjustment sets in the literature , so if the adjustment were with reference to $\mathcal{G}$, one could run these algorithms on each $X_{i}$ independently to find each backdoor admissible set $\bm{Z}_{i}$. However, each action $X_{i}$ has its $\bm{Z}_{i}$ in the manipulated graph $\mathcal{G}^{\prime}_{i}$, which is dependent on the adjustment used for future actions $X_{i+1:n}$. This means that certain adjustment sets $\bm{Z}_{j}$ for $X_{j>i}$ will make there not exist any $\bm{Z}_{i}$ for $X_{i}$ in $\mathcal{G}^{\prime}_{i}$ that satisfies the criterion! As an example, in Fig. 2(c), $X_{2}$ can use any combination of $Z,X_{1},W$ as a valid adjustment set $\bm{Z}_{2}$. However, if $Z$ comes after $X_{1}$ in temporal order, only $\bm{Z}_{2}=\{Z\}$ leads to valid imitation over $\bm{X}=\{X_{1},X_{2}\}$.

The direct approach towards solving this problem would involve enumerating all possible backdoor admissible sets $\bm{Z}_{i}$ for each $X_{i}$, but there are both exponentially many backdoor admissible sets $\bm{Z}_{i}$, and exponentially many combinations of sets over multiple $X_{i:n}$. Such a direct exponential enumeration is not feasible in practical settings. To address these issues, this section will see the development of Algorithm 1, which finds a sequential $\pi$-backdoor admissible set $\bm{Z}_{1:n}$ with regard to actions $\bm{X}$ in a causal diagram $\mathcal{G}$ in polynomial time, if such a set exists.

Before delving into the details of Algorithm 1, we describe a method intuitively motivated by the “Nearest Separator" from that can generate a backdoor admissible set $\bm{Z}_{i}$ for a single independent action $X_{i}$ in the presence of unobserved variables. While it does not solve the problem of multiple actions due to the issues listed above, it is a building block for Algorithm 1.

Consider the Markov Boundary (minimal Markov Blanket, ) for a set of nodes $\bm{O}^{X}\subseteq\bm{O}$, which is defined as the minimal set $\bm{Z}\subset\bm{O}\setminus\bm{O}^{X}$ such that $(\bm{O}^{X}\perp\!\!\!\perp\bm{O}\setminus\bm{O}^{X}|\bm{Z})$. This definition can be applied to graphs with latent variables, where it can be constructed in terms of c-components:

Given $\bm{O}^{X}\subseteq\bm{O}$, the Markov Boundary of $\bm{O}^{X}$ in $\bm{G}$ is $\mathit{Pa}^{+}(\bm{C}(\mathit{Ch}^{+}(\bm{O}^{X})))\setminus\bm{O}^{X}$

If there is a set $\bm{Z}\subseteq\before(X_{i})$ that satisfies the backdoor criterion for $X_{i}$ with respect to $Y$, then taking $\mathcal{G}^{Y}$ as the ancestral graph of $Y$, the Markov Boundary $\bm{Z}^{\prime}$ of $X_{i}$ in $\mathcal{G}^{Y}_{\underline{X_{i}}}$ has $\bm{Z}^{\prime}\subseteq\before(X_{i})$, and also satisfies the backdoor criterion in $\mathcal{G}$. The Markov Boundary can therefore be used to generate a backdoor adjustment set wherever one exists.

A naïve algorithm that uses the Markov Boundary of $X_{i}\in\bm{X}$ in $(\mathcal{G}^{\prime}_{i})^{Y}_{\underline{X_{i}}}$ as the corresponding $\bm{Z}_{i}$, and returns a failure whenever $\bm{Z}_{i}\notin\before(X_{i})$ for the sequential $\pi$-backdoor is equivalent to the existing literature on finding backdoor-admissible sets. It cannot create a valid sequential $\pi$-backdoor for Figure 2(c), since $X_{2}$ would have $\bm{Z}_{2}=\{W\}$, but no adjustment set exists for $X_{1}$ that d-separates it from $Y$ in the resulting $\mathcal{G}^{\prime}_{1}$. We must take into account interactions between actions encoded in $\mathcal{G}^{\prime}_{i}$.

We notice that an $X_{i}$ does not require a valid adjustment set if it is not an ancestor of $Y$ in $\mathcal{G}^{\prime}_{i}$ (i.e. $X_{i}$ does not need to satisfy (1) of Definition 2.3 if it can satisfy (2)). Furthermore, even if $X_{i}$ is an ancestor of $Y$ in $\mathcal{G}^{\prime}_{i}$, and therefore must satisfy condition (1) of Definition 2.3, any elements of its c-component that are not ancestors of $Y$ in $\mathcal{G}^{\prime}_{i}$ won’t be part of $(\mathcal{G}^{\prime}_{i})^{Y}$, and therefore don’t need to be conditioned.

It is therefore beneficial for an action $X_{j}$ to have a backdoor adjustment set that maximizes the number of nodes that are not ancestors of $Y$ in $\mathcal{G}^{\prime}_{j-1}$, so that actions $X_{i<j}$ can satisfy (2) of Definition 2.3 if possible, and have the smallest possible c-components in $(\mathcal{G}^{\prime}_{i})^{Y}$ (increasing likelihood that backdoor set $\bm{Z}_{i}\subseteq\before(X_{i})$ exists if $X_{i}$ must satisfy condition (1)).

To demonstrate this intuition, we once again look at Figure 2(c), focusing only on action $X_{2}$. If we were to use $\{W\}$ as $\bm{Z}_{2}$, we still have the same set of ancestors of $Y$ in $\mathcal{G}^{\prime}_{1}$. If we switch to $\{X_{1}\}$, then $W$ would no longer be an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$ - meaning that $X_{1}$ is better as a backdoor adjustment set for $X_{2}$ than $\{W\}$ if we only know that $X_{2}$ is an action (i.e. $W$ would directly satisfy (2) of Definition 2.3 if it were the other action). Finally, using $\{Z\}$ as $\bm{Z}_{2}$ makes both $X_{1}$ and $W$ no longer ancestors of $Y$ in $\mathcal{G}^{\prime}_{1}$, meaning that it is the best option for the adjustment set $\bm{Z}_{2}$.

FindOx in Algorithm 1 employs the above ideas to iteratively grow a set $\bm{O}^{X}\subseteq\bm{O}$ of ancestors of $\bm{X}$ (and including $\bm{X}$) in $\mathcal{G}^{Y}$ whose elements (possibly excluding $\bm{X}$) will not be ancestors of $Y$ once the actions in their descendants are taken. That is, an element $O_{i}\in\bm{O}^{X}$ where $\mathit{ch}^{+}(O_{i})\subset\bm{O}^{X}$ is not present in $(\mathcal{G}^{\prime}_{i})^{Y}$ for all actions $X_{i}$ that come before it in temporal order. Combined with the Markov Boundary, FindOx can be used to generate sequential $\pi$-backdoors.

We exemplify the use of Algorithm 1 through Figure 2(c). $\mathscr{O}^{X}$ represents a map of observed variables which are not ancestors of $Y$ in $\mathcal{G}^{\prime}_{i<j}$ to the earliest action $X_{j}$ in their descendants. The keys of $\mathscr{O}^{X}$ will be the set $\bm{O}^{X}$. Considering the temporal order $\{X_{1},Z,W,X_{2},Y\}$, the algorithm starts from the last node, $Y$, which has no children and is not an element of $\bm{X}$, so is not added to $\mathscr{O}^{X}$. It then carries on to $X_{2}$, which is checked for the existence of a valid backdoor adjustment set. Here, the subgraph of the c-component of $X_{2}$ and its parents (HasValidAdjustment) is simply $W<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>→</mo></mrow><annotation encoding="application/x-tex">\rightarrow</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">→</span></span></span></span></span>X_{2}$, meaning that we can condition on $W$ to make $X_{2}$ independent of all other observed variables, including $Y$, in $\mathcal{G}_{\underline{X_{2}}}$ ($W$ is a Markov Boundary for $X_{2}$ in $\mathcal{G}_{\underline{X_{2}}}$). The algorithm therefore sets $\mathscr{O}^{X}=\{X_{2}:X_{2}\}$, because $X_{2}$ is an action with a valid adjustment set. Notice that if the algorithm returned at this point with $\bm{O}^{X}=\{X_{2}\}$, the Markov Boundary of $\bm{O}^{X}$ in $\mathcal{G}_{\underline{X_{2}}}$ is $W$, and corresponds to a sequential $\pi$-backdoor for the single action $X_{2}$ (ignoring $X_{1}$), with policy $\pi(X_{2}|W)=P(X_{2}|W)$.

Next, $W$ has $X_{2}$ as its only child, which itself maps to $X_{2}$ in $\mathscr{O}^{X}$. The subgraph of $W$’s c-component and its parents is $X_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>→</mo></mrow><annotation encoding="application/x-tex">\rightarrow</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">→</span></span></span></span></span>W$, giving $(W\perp\!\!\!\perp\bm{O}|X_{1})_{\mathcal{G}_{\underline{W}}}$, and $\{X_{1}\}\subseteq\before(X_{2})$, allowing us to conclude that there is a backdoor admissible set for $X_{2}$ where $W$ is no longer an ancestor of $Y$. We set $\mathscr{O}^{X}=\{X_{2}:X_{2},W:X_{2}\}$, and indeed with $\bm{O}^{X}=\{X_{2},W\}$, the Markov Boundary of $\bm{O}^{X}$ in $\mathcal{G}_{\underline{X_{2}}}$ is $X_{1}$, and is once again a valid sequential $\pi$-backdoor for the single action $X_{2}$ (ignoring $X_{1}$), with policy $\pi(X_{2}|X_{1})=P(X_{2}|X_{1})$. The $W$ in $\bm{O}^{X}$ was correctly labeled as not being an ancestor of $Y$ after action $X_{2}$ is taken.

Since $Z$ doesn’t have its children in the keys of $\mathscr{O}^{X}$, and is not an element of $\bm{X}$, it is skipped, leaving only $X_{1}$. $X_{1}$’s children ($W$) are in $\mathscr{O}^{X}$, we check conditioning using $X_{2}$ instead of $X_{1}$ (i.e. we check if $X_{1}$ can satisfy (2) of Definition 2.3, and not be an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$). This time, we have $X_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>↔</mo></mrow><annotation encoding="application/x-tex">\leftrightarrow</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">↔</span></span></span></span></span>Z$ as the c-component subgraph, and $Z$ comes before $X_{2}$, satisfying the check ($X_{1}\perp\!\!\!\perp Z|Z$) in HasValidAdjustment, resulting in $\mathscr{O}^{X}=\{X_{2}:X_{2},W:X_{2},X_{1}:X_{2}\}$, and $\bm{O}^{X}=\{X_{2},W,X_{1}\}$. Indeed, the Markov Boundary of $\bm{O}^{X}$ in $\mathcal{G}_{\underline{X_{2}}}$ is $\{Z\}$, and we can construct a valid sequential $\pi$-backdoor by using $\bm{Z}_{1}=\{\}$ and $\bm{Z}_{2}=\{Z\}$, where $X_{1}$ is no longer an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$! In this case, we call $X_{2}$ a “boundary action", because it is an ancestor of $Y$ in $\mathcal{G}^{\prime}_{2}$. On the other hand, $X_{1}$ is not a boundary action, because it is not an ancestor of $Y$ in $\mathcal{G}^{\prime}_{1}$.

The set $\bm{X}^{B}\subseteq\bm{X}$ called the “boundary actions" for $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$ are all elements $X_{i}\in\bm{X}\cap\bm{O}^{X}$ where $\mathit{ch}^{+}(X_{i})\not\subseteq\bm{O}^{X}$.

Algorithm 1 is general: the set $\bm{O}^{X}$ returned by FindOx can always be used in conjunction with its Markov Boundary to construct a sequential $\pi$-backdoor if one exists:

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$, and $\bm{X}^{\prime}:=\bm{O}^{X}\cap\bm{X}$. Taking $\bm{Z}$ as the Markov Boundary of $\bm{O}^{X}$ in $\mathcal{G}^{Y}_{\underline{X^{\prime}}}$ and $\bm{X}^{B}$ as the boundary actions of $\bm{O}^{X}$, the sets $\bm{Z}_{i}=(\bm{Z}\cup\bm{X}^{B})\cap\before(X^{\prime}_{i})$ for each $X^{\prime}_{i}\in\bm{X}^{\prime}$ are a valid sequential $\pi$-backdoor for $(\mathcal{G},\bm{X}^{\prime},Y)$.

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. Suppose that there exists a sequential $\pi$-backdoor for $\bm{X}"\subseteq\bm{X}$. Then $\bm{X}"\subseteq\bm{O}^{X}$.

Combined together, Lemmas 3.3 and 3.2 show that FindOx finds the maximal subset of $\bm{X}$ where a sequential $\pi$-backdoor exists, and the adjustment sets $\bm{Z}_{1:n}$ can be constructed using the subset of a Markov Boundary over $\bm{O}^{X}$ that comes before each corresponding action $X_{i}$ (Lemma 3.2). FindOx is therefore both necessary and sufficient for generating a sequential $\pi$-backdoor:

Let $\bm{O}^{X}$ be the output of $\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. A sequential $\pi$-backdoor exists for $(\mathcal{G},\bm{X},Y)$ if and only if $\bm{X}\subseteq\bm{O}^{X}$.

Necessity of Sequential π\pi-Backdoor for Imitation

In this section, we show that the sequential $\pi$-backdoor is necessary for imitability, meaning that the sequential $\pi$-backdoor is complete.

A given imitation problem can have multiple possible conditioning sets satisfying the sequential $\pi$-backdoor, and a violation of the criterion for one set does not preclude the existence of another that satisfies the criterion. To avoid this issue, we will use the output of Algorithm FindOx, which returns a unique set $\bm{O}^{X}$ for each problem:

Let $\bm{O}^{X}:=\textsc{FindOx}(\mathcal{G},\bm{X},Y)$. Suppose $\exists X_{i}\in\bm{X}$ s.t. $X_{i}\in\bm{X}\setminus\bm{O}^{X}$. Then $\bm{X}$ is not imitable with respect to $Y$ in $\mathcal{G}$.

Our next proposition establishes the necessity of the sequential $\pi$-backdoor criterion for the imitability of the expert’s performance (Definition 2.1), which follows immediately from Lemmas 4.1 and 3.1.

If there do not exist adjustment sets satisfying the sequential $\pi$-backdoor criterion for $(\mathcal{G},\bm{X},Y)$, then $\bm{X}$ is not imitable with respect to $Y$ in $\mathcal{G}$.

The proof of Lemma 4.1 relies on the construction of an adversarial SCM for which $Y$ can detect the imitator’s lack of access to the latent variables. For example, in Figure 2(a), $Z$ can carry information about the latent variable $U$ to $Y$, and is only determined after the decision for the value of $X$ is made. Setting $U\sim Bern(0.5),X:=U,Z:=U,Y:=X\oplus Z$ leaves the imitator with a performance of ${\rm I\kern-3.00003ptE}[\hat{Y}]=0.5$, while the expert can get perfect performance (${\rm I\kern-3.00003ptE}[Y]=1$).

Another example with similar mechanics can be seen in Figure 2(c). If the variables are determined in the order $(X_{1},W,X_{2},Z,Y)$, then the sequence of actions is not imitable, since $Z$ can transfer information about the latent variable $U$ to $Y$, while $X_{2}$ has no way of gaining information about $U$, because the action at $X$ needed to be taken without context.

Finally, observe Figure 2(d). If $Z$ is determined after $X_{1}$, the imitator must guess a value for $X_{1}$ without this side information, which is then combined with $U_{2}$ at $W$. An adversary can exploit this to construct a distribution where guessing wrong can be detected at $Y$ as follows: $U_{1}\sim Bern(0.5)$, $Z,X:=U_{1}$, $U_{2}\sim(Bern(0.5),Bern(0.5))$ (that is, $U_{2}$ is a tuple of two binary variables, or a single variable with a uniform domain of $0,1,2,3$). Then setting $W=U_{2}[Z]$ ($[]$ represents array access, meaning first element of tuple if $Z=0$ and second if $Z=1$), and $X_{2}:=W$, $Y:=(U_{2}[X_{1}]==X_{2})$ gives ${\rm I\kern-3.00003ptE}[Y]=1$ only if $\pi_{1}$ guesses the value of $U_{1}$, meaning that the imitator can never achieve the expert’s performance. This construction also demonstrates non-imitability when $X_{1}$ and $Z$ are switched (i.e., Figure 2(c) with $W\leftrightarrow Y$ added, and $X_{1}$ coming before $Z$ in temporal order).

Due to these results, after running Algorithm 1 on the domain’s causal structure, the imitator gets two pieces of information:

Is the problem imitable? In other words, is it possible to use only observable context variables, and still get provably optimal imitation, despite the expert and imitator having different information?

If so, what context should be included in each action? Including/removing certain observed covariates in an estimation procedure can lead to different conclusions/actions, only one of which is correct (known as “Simpson’s Paradox” in the statistics literature ). Furthermore, as demonstrated in Figure 2(c), when performing actions sequentially, some actions might not be imitable themselves ($X_{1}$ if $Z$ after $X_{1}$), which leads to bias in observed descendants ($W$) - the correct context takes this into account, using only covariates known not to be affected by incorrectly guessed actions.

Finally, the obtained context $\bm{Z}_{i}$ for every action $X_{i}$ could be be used as input to existing algorithms for behavioral cloning, giving an imitating policy with an unbiased result.

Simulations

We performed 2 experiments (for full details, refer to [9, Appendix B]), comparing the performance of 4 separate approaches to determining which variables to include in an imitating policy:

All Observed (AO) - Take into account all variables available to the imitator at the time of each action. This is the approach most commonly used in the literature.

Observed Parents (OP) - The expert used a set of variables to take an action - use the subset of these that are available to the imitator.

$\pi$-Backdoor - In certain cases, each individual action can be imitated independently, so the individual single-action covariate sets are used.

Sequential $\pi$-Backdoor (ours) - The method developed in this paper, which takes into account multiple actions in sequence.

The first simulation consists of running behavioral cloning on randomly sampled distributions consistent with a series of causal graphs designed to showcase aspects of our method. For each causal graph, 10,000 random discrete causal models were sampled, representing the environment as well as expert performance, and then the expert’s policy $\bm{X}$ was replaced with imitating policies approximating $\pi(X_{i})=P(X_{i}|ctx(X_{i}))$, with context $ctx$ determined by each of the 4 tested methods in turn. Our results are shown in Table 1, with causal graphs shown in the first column, temporal ordering of variables in the second column, and absolute distance between expert and imitator for the 4 methods in the remaining columns.

In the first row, including $Z$ when developing a policy for $\bm{X}$ leads to a biased answer, which makes the average error of using all observed covariates (red) larger than just the sampling fluctuations present in the other columns. Similarly, $Z$ needs to be taken into account in row 2, but it is not explicitly used by $\bm{X}$, so a method relying only on observed parents leads to bias here. In the next row, $Z$ is not observed at the time of action $X_{1}$, making the $\pi$-backdoor incorrectly claim non-imitability. Our method recognizes that $X_{2}$’s policy can fix the error made at $X_{1}$, and is the only method that leads to an unbiased result. Finally, in the 4th row, the non-causal approaches have no way to determine non-imitability, and return biased results in all such cases.

The second simulation used a synthetic, adversarial causal model, enriched with continuous data from the HighD dataset altered to conform to the causal model, to demonstrate that different covariate sets can lead to significantly different imitation performance. A neural network was trained for each action-policy pair using standard supervised learning approaches, leading to the results shown in Figure 4. The causal structure was not imitable from the single-action setting, so the remaining 3 methods were compared to the optimal reward, showing that our method approaches the performance of the expert, whereas non-causal methods lead to biased results. Full details of model construction, including the full causal graph are given in [9, Appendix B]

Limitations & Societal Impact

There are two main limitations to our approach: (1) Our method focuses on the causal diagram, requiring the imitator to provide the causal structure of its environment. This is a fundamental requirement: any agent wishing to operate in environments with latent variables must somehow encode the additional knowledge required to make such inferences from observations. (2) Our criterion only takes into consideration the causal structure, and not the associated data $P(\bm{o})$. Data-dependent methods can be computationally intensive, often requiring density estimation. If our approach returns “imitable", then the resulting policies are guaranteed to give perfect imitation, without needing to process large datasets to determine imitability.

Finally, advances in technology towards improving imitation can easily be transferred to methods used for impersonation - our method provides conditions under which an imposter (imitator) can fool a target ($Y$) into believing they are interacting with a known party (expert). Our method shows when it is provably impossible to detect an impersonation attack. On the other hand, our results can be used to ensure that the causal structure of a domain cannot be imitated, helping mitigate such issues.

Conclusion

Great care needs to be taken in choosing which covariates to include when determining a policy for imitating an expert demonstrator when expert and imitator have different views of the world. The wrong set of variables can lead to biased, or even outright incorrect predictions. Our work provides general and complete results for the graphical conditions under which behavioral cloning is possible, and provides an agent with the tools needed to determine the variables relevant to its policy.

Funding Transparency

The team is supported in part by funding from the NSF, Amazon, JP Morgan, and The Alfred P. Sloan Foundation, as well as grants from NSF IIS-1704352 and IIS-1750807 (CAREER).

References