Year: 2021

Abstract:
We develop algorithms for imitation learning from policy data that was corrupted by unobserved confounders. Sources of such confounding include (a) persistent perturbations to actions or (b) the expert responding to a part of the state that the learner does not have access to. When a confounder affects multiple timesteps of recorded data, it can manifest as spurious correlations between states and actions that a learner might latch on to, leading to poor policy performance. To break up these spurious correlations, we apply modern variants of the classical instrumental variable regression (IVR) technique, enabling us to recover the causally correct underlying policy without requiring access to an interactive expert. In particular, we present two techniques, one of a generative-modeling flavor (DoubIL) that can utilize access to a simulator and one of a game-theoretic flavor (ResiduIL) that can be run entirely offline. We discuss, from the perspective of performance, the types of confounding under which it is better to use an IVR-based technique instead of behavioral cloning and vice versa. We find both of our algorithms compare favorably to behavioral cloning on a simulated rocket landing task.

heading: 1 INTRODUCTION
text: Much of the theory of imitation learning (IL) indicates that with enough demonstrations, we should be able to accurately recover the expert’s policy. When we apply IL algorithms in practice however, we sometimes see them produce manifestly incorrect estimates of the expert’s policy (Muller et al., 2006; Codevilla et al., 2019; de Haan et al., 2019; Bansal et al., 2018; Kuefler et al., 2017). One possible reason for this phenomenon is that empirically, we only have access to noisy recordings of what the expert did. This critical detail has been thus far neglected by most prior theoretical work in imitation learning. We focus in this paper on how best to learn from two kinds of noisy data:
• Exogenous noise: When we observe expert actions corrupted by a persistent noise (e.g. a faulty joystick that persistently perturbs actions before they are executed in the game).
• Endogenous noise: When we do not observe the full state an expert used to pick an action (e.g. the learner not knowing there’s an enemy behind a door).
The net effect of either kind of persistent noise (more formally, an unobserved confounder) is to introduce temporal correlations in the recorded actions that do not have their true cause in the recorded state. For example, consider recordings of an expert driver slowing down at a stop sign. If all we present the learner with as state input is whether the expert was slowing down at the last timestep, they will likely learn to simply repeat the expert’s past action. Thus, once the car begins to slow down, it continues to slow down, regardless of whether there is a stop sign present. At a more abstract level, these sorts of inertia problems can result from temporal correlations between pairs of actions (e.g. the effect of the stop sign) being reflected in the state (e.g. the past action variable), leading to spurious correlations between state and action that the learner might unfortunately latch onto (e.g. repeating the past action).
What should we hope to learn then in these confounded settings? Given we do not have access to the unobserved confounder, a reasonable choice is to ensure that we match the behavior of an expert that has access to the same information we do. That is, if we could query the expert for an action with only the information we have available, we should strive to produce an action that matches
this queried action. While applying an interactive imitation learning algorithm (Ross et al., 2011) would allow us to collect a dataset uncorrupted by confounding, a queryable expert is not a realistic assumption for many domains. We therefore focus on approaches for the off-policy setting. We base our algorithms on a technique from econometrics for dealing with confounding in recorded data known an instrumental variable regression (IVR) (Angrist et al., 1996). The high-level idea of IVR is to leverage an instrument, a source of random variation independent of the confounder, to deconfound inputs to a learning procedure via conditioning on the instrument. In dynamical systems, history can act as this source of variation, as it is unaffected by future confounding (Hefny et al., 2015). Our key insight is that we can leverage past states as instruments to break the spurious correlation between states and actions caused by an unobserved confounder.
Our work provides the following contributions:
1. We formalize confounding in imitation learning. We provide a structural causal model that captures inertia effects that result from temporally correlated exogenous or endogenous noise. We also derive a test to detect whether this sort of confounding is present in a dataset.
2. We present a unified derivation of modern instrumental variable regression techniques. We show how two recent extensions of the classical IVR technique share a common structure. We also extend the theoretical analysis of previous work by deriving accuracy bounds.
3. We provide two novel algorithms to deal with confounding in imitation learning. We derive two novel IVR-based algorithms:
• DoubIL is a generative modeling approach that and can utilize access to a simulator for reduced sample complexity. • ResiduIL is a simulator-free, game-theoretic approach.
We derive performance bounds for policies produced by these algorithms under exogenous noise. We empirically investigate the effect of the persistence of the confounder on this bound. We also compare the performance of these approaches to behavioral cloning under endogenous noise.

heading: 2 RELATED WORK
text: Imitation Learning. Broadly speaking, imitation learning approaches can be grouped into three classes: offline, online, and interactive. Our work is most similar to offline imitation learning algorithms (e.g. Behavioral Cloning (Pomerleau, 1989), ValueDice (Kostrikov et al., 2019), AdVIL (Swamy et al., 2021)) that operate purely on collected data. Unlike previous work however, we consider the effect of unobserved confounding. Our work shares the goal of interactive imitation learning algorithms (e.g. DAgger (Ross et al., 2011), AggreVaTe (Ross & Bagnell, 2014)), in that we seek to match the output of a query to the expert. However, we focus on matching the output of a query on recorded data, rather than on learner rollouts, as is standard for interactive approaches. This is because the confounder decouples the actions recorded in the data and queried actions. Zhang et al. (2020) consider imitation learning through the lens of causal inference but focus on the one-step setting, while we consider multiple timesteps. Kumor et al. (2021) contemporaneously consider the
multi-step setting and come to similar conclusions as us about the challenges of endogenous noise. They derive a necessary and sufficient structural condition for successful imitation learning, while we focus on practical algorithms with performance guarantees for a particular graphical model under exogenous noise. In contrast to imitation learning methods that seeks to match moments of the expert’s behavior (Swamy et al., 2021), we focus only on matching average expert actions. We leave matching arbitrary moments to future work.
Inertia Effects in Imitation Learning. Several authors have empirically observed a latching effect in policies trained via imitation learning: (Muller et al., 2006; Codevilla et al., 2019; de Haan et al., 2019; Bansal et al., 2018; Kuefler et al., 2017), where learned policies tend to inappropriately repeat the same action. We seek to provide a plausible explanation and correction for the phenomenon reported in these works, and list several examples in Table 1. We note that when attempting to explain inertia effects, de Haan et al. (2019) propose causal confounding as the root cause of the error. However, as previously pointed out by Spencer et al. (2021), there is no actual confound in the theoretical or empirical examples in the work of de Haan et al. (2019). This is because the learner observes all of the variables the expert was using to make decisions.
Instrumental Variable Regression. The classical approach to instrumental variable regression (Wright, 1928) is a two-stage least squares procedure (e.g. in Angrist et al. (1996)’s textbook). We focus on the more general nonlinear setting and instead base our approaches on the more recent DEEPIV (Hartford et al., 2017) and AGMM (Dikkala et al., 2020). We present extensions to the work in these papers, including a unified derivation of both methods and error analysis for DEEPIV.

heading: 3 A BRIEF REVIEW OF INSTRUMENTS IN CAUSAL MODELING
text: We begin by discussing the concept of an instrument before deriving our algorithmic approaches in a simplified, non-sequential setting. Let X , Y , and Z be random variables on (potentially infinite) sample spaces X , Y , and Z . Assume that X , Y , and Z have the causal, rather than statistical, dependency structure in Fig. 2. Given a dataset of (x, y, z) tuples, we are interested in determining the causal relationship between X and Y , E[Y |do(x)], where do(·) is the interventional operator of Pearl et al. (2016). Intuitively, E[Y |do(x)] is the expected value of Y when we intervene and set X = x, rather than observe such an X . In the SCM to the right, h(x) = E[Y |do(x)]. Because of the presence of an unobserved confounder, U , that affects both X and Y , standard regression (e.g. Ordinary Least Squares or OLS) generically produces inconsistent estimates. Coarsely, this occurs because OLS will over-estimate the influence of the parts ofX that are affected by the confounder. If we only have observational data and are unable to perform randomized control trials, a canonical technique to recover h is IVR (Winship & Morgan, 1999). Formally, an instrument Z must satisfy three structural conditions:
1. Unconfounded Instrument: Z ⊥⊥ U – i.e. independent randomization from confounder. 2. Exclusion: Z ⊥⊥ Y |X,U – i.e. no extraneous paths. 3. Relevance: Z 6⊥⊥ X – i.e. conditioning has an effect.
Z satisfies these three conditions in the SCM of Fig. 2. 1 Without loss of generality, we assume that E[U ] = 0. This allows us to concisely derive a set of conditional moment restrictions (CMR):
0 = E[U ] = E[U |z] = E[Y − h(X)|z] (1) ⇒ ∀z ∈ Z, E[Y |z] = E[h(X)|z]. (2)
In words, these constraints are saying that a necessary condition for recovery of h(x) is that for all values of the instrument, the actual and predicted expected values of Y |Z are equal. We further assume that noise U enters additively to Y ,2 and write out the following equations:
X = g(Z,U, V ), Y = h(X) + U. (3)
We now derive an appropriate loss function for finding an ĥ that approximately satisfies the CMR. If we only have finite samples and can therefore only estimate conditional expectations up to some tolerance, it is natural to relax the CMR to
minĥ∈H, δ 1 2Ez[δ 2 z ] s.t. |E[Y − ĥ(X)|z]| ≤ δz, δz ≥ 0, ∀z ∈ Z, (4)
where the δz are slack variables. Then, the Lagrangian (with the natural P (z)-weighted inner product that captures how often each we expect each z to occur) is
L(ĥ, δ,λ) = ∑ z∈Z P (z)λz(E[Y − ĥ(X)|z]− δz) + P (z) 1 2 δ2z , (5)
where λ is the vector of Lagrange multipliers. By the stationarity component of the KKT conditions,
∇δzL(ĥ, δ,λ) = −P (z)λz + P (z)δz = 0, (6) implying that δz = λz . Plugging this back into the Lagrangian, we can simplify our function to
L(ĥ,λ) = ∑ z∈Z P (z)λzE[Y − ĥ(X)|z]− P (z) 1 2 λ2z. (7)
We refer to (7) as the Regularized Lagrangian or ReLa for short. Now, solving for the optimal Lagrange multipliers via stationarity, we arrive at
∇λzL(ĥ,λ) = P (z)E[Y − ĥ(X)|z]− P (z)λz = 0, (8) which implies the optimal λz is equal to E[Y − ĥ(X)|z]. Plugging this back into (7) recovers the loss function,
L(ĥ) = ∑ z∈Z P (z)E[Y − ĥ(X)|z]2 = PRMSE2(ĥ). (9)
This expression is the square of the Projected Root Mean Squared Error (PRMSE) of Chen & Pouzo (2012). To recap, by minimizing Eq. 9, we are attempting to find an ĥ that approximately satisfies the CMR. Minimizing PRMSE is a necessary condition for recovering E[Y |do(X)]. For it to be a sufficient condition, one needs the natural identifiability assumptions – we refer interested readers to Chen & Pouzo (2012) for a more thorough discussion.

heading: 3.1 GENERATIVE MODELING APPROACH
text: How should we minimize the PRMSE then? One option is learning the distribution P (X|z) = g(z), passing samples from it to a candidate ĥ, and trying to match E[Y |z]. This is a generalization of the standard Two-Stage Least Squares (2SLS) (Angrist et al., 1996) procedure to nonlinear functions. The nonlinearity of the second stage means that one cannot simply compute the first moment of the P (X|z) distribution, which is recovered by linearly regressing from X to Z in the 2SLS procedure. This sort of approach was first proposed for the IVR setting by Hartford et al. (2017) and amounts to first learning a g(z) (e.g. via maximum likelihood estimation) and then solving
min ĥ∈H
EZ [ (E[Y |z]− EX̂∼g(z)[ĥ(X̂)])2 ] . (10)
The work of Hartford et al. (2017) did not have theoretical analysis regarding the effect of errors in g(z) upon attempts to learn h(x). We prove the following in Appendix A:
1The inclusion of V makes our model a generalization of the standard IVR model, so we confirm the validity of the instrument in Appendix A.
2Without this assumption, one can only upper/lower bound h(x) (Balke & Pearl, 2013).
Theorem 1. Assume we learn a g(z) s.t. maxĥ∈H EZ [(Ex∼g(z)[ĥ(x)] − Ex∼P (X|z)[ĥ(x)])2] ≤ δ. Then, optimizing (10) to value corresponds to recovering a ĥ(x) s.t. PRMSE(ĥ) ≤ √ δ + √ .

heading: 3.2 GAME-THEORETIC APPROACH
text: One can also proceed by instead solving the two-player zero-sum game with the ReLa (7) as the payoff. Denoting by f ∈ F = {Z → R} the function that maps z’s to their Lagrange multipliers, we can write this game as
min ĥ∈H max f∈F
E[2(Y − ĥ(X))f(Z)− f(Z)2]. (11)
This game is the core objective of the AGMM method of Dikkala et al. (2020). Importantly, one does not need to learn a generative model of P (X|z) for these sorts of game-theoretic approaches. We prove the following theorem in Appendix A: Theorem 2. Assume that H and F are bounded, closed under negation, convex, compact, and that h ∈ H and ∀ĥ ∈ H, f(z) = E[Y − ĥ(X)|z] ∈ F . Then, an -approximate Nash equilibrium of (11) corresponds to recovering a ĥ(x) s.t. PRMSE(ĥ) ≤ √ . One can find such an equilibrium via a standard reduction to no-regret online learning (Freund & Schapire, 1997).
In summary, one can frame nonlinear IVR as a generative modeling or game-theoretic problem, leading to different error characteristics. We now turn our attention to applying these methods to imitation learning with unobserved confounders.

heading: 4 CAUSAL CONFOUNDING IN IMITATION LEARNING
text: We begin with a brief, intuitive sketch to illustrate the challenges of confounding for IL: consider an expert trying to fly a quadcopter straight but their actions being perturbed by wind (i.e. a form of exogenous noise). Because it attempts to reproduce expert actions, behavioral cloning would reproduce these deviations, producing trajectories that deviate even further from a straight path in a windy environment. In contrast, by filtering out the effects of the confounder, a policy trained via IVR would only be affected by the wind present at test time and therefore produce trajectories similar to those of the expert.
We now formalize this sort of confounding and how one can use IVR to mitigate its effects. We use ∆(S) to mean the set of distributions over S and focus on a Markov Decision Process (MDP) parameterized by 〈S,A, T , r, T 〉, where S is the state space, A
is the action space, T : S × A → ∆(S) is the transition operator, r : S × A → [−1, 1] is the reward function, and T is the horizon of the problem. Let J(π) = Eτ∼π[ ∑T t=1 r(st, at)], Π ⊆ {S → ∆(A)} be the policy class we optimize over and dπ be the visitation distribution of policy π. In the presence of unobserved confounding, the trajectories generated by the expert can be captured by the structural causal model (SCM) in Fig. 4. 3 Fig. 4 captures both the exogenous and endogenous noise settings. In the exogenous noise setting, the confounder ut−1 could be a persistent noise that affects pairs of actions, while in the endogenous noise setting, ut−1 can be thought of as a response to a part of the state that the learner does not have access to (see Table 1 for several example) In either setting, the confounding travels through the dynamics to influence the next state, leading to spurious correlations between the recorded states and actions. We can also see this correlative effect by writing out the structural equations:
X = st = T (st−1, at−1) = T (st−1, πE(st−1) + ut−1 + ut−2) (12) Y = at = πE(st) + ut + ut−1. (13)
3One technically needs to add another input to πE (i.e. πE(s,R), where R is a random input) to allow for a non-deterministic expert. In this work, we focus on techniques for minimizing the PRMSE, for which matching average expert actions is sufficient. Thus, we suppress the dependence on the other input.
Fig. 4 also tells us that Z = st−1 satisfies the three conditions to make it a valid instrument for countering the effects of U = ut−1. Intuitively, this is because the past state is independent of the current confounder, allowing it to function as an independent source of randomness. One can imagine longer time-scale correlations induced between actions than just one step confounding – our approaches naturally extend to this setting by using a state further back in the past as the instrument.
Unlike standard imitation learning approaches like behavior cloning which attempt to recover E[a|s], an approach based on IVR enables us to instead recover the interventional effect of the policy E[πE(s)|s] = E[a|do(s)]. Conceptually, E[a|do(s)] is asking what the expert would do on average if they were placed in state s, i.e. the kind of answer we would get from a queryable expert in DAgger (Ross et al., 2011) or DAeQuIL (Swamy et al., 2021). However, as we are only interested in the result of queries on states from expert demonstrations, we are able to get a similar effect via IVR to an interactive approach without
requiring access to a queryable expert. We now build upon this intuition to derive two algorithms.

heading: 5 ALGORITHMS FOR CAUSAL IMITATION LEARNING
text: We now present two approaches for causal imitation learning that can be seen as applications of the generative modeling and game-theoretic approaches of Sec. 3. At their core, both algorithms are attempting to minimize a PRMSE objective,
min π∈Π E(s,s′,a′)∼dπE [(E[a ′ − π(s′)|s])2], (14)
instead of the usual IL objective,
min π∈Π E(s,a)∼dπE [(a− π(s)) 2]. (15)
In both the exogenous and endogenous settings, minimizing equation 14 corresponds to recovering E[a|do(s)]. What differs is the performance implications of doing so, as we now discuss further.

heading: 5.1 EXOGENOUS NOISE
text: Exogenous noise is present both in the demonstrations as well as at test time. Our goal in this setting is to eliminate the effect of the confounder so at test time we do not needlessly reproduce its effects (e.g. the increased swerving in our quadcopter example). Notice that under exogenous noise, minimizing (15) to 0 would not recover the expert’s policy while minimizing Equation (14) would. First, let a distribution P (U) be c-Total Variation stable (Bassily et al., 2021) if:
‖a− b‖2 ≤ δ ⇒ dTV (a+ U, b+ U) ≤ cδ. (16) This property is satisfied by a wide variety of distributions. For example, for standard normal random variables, c = 1/2. Next, in our setting, the measure of ill-posedness (Dikkala et al., 2020; Chen & Pouzo, 2012) is
κ(Π) = sup π∈Π
√ Es∼dπE [(πE(s)− π(s))2]√
Es,s′,a′∼dπE [E[a ′ − π(s′)|s]]2
= sup π∈Π RMSE(π) PRMSE(π) . (17)
We prove the following bound on policy performance in Appendix B:
Theorem 3. Assume P (U) is c-TV Stable exog. noise, πE is deterministic, and let κ(Π) be the measure of the ill-posedness of the problem. Then, PRMSE(π) ≤ ⇒ J(πE)− J(π) ≤ cκ(Π) T 2.
Intuitively, κ(Π) measures the strength of the strength of the instrument. Consider the extreme case where s′ = s. Then, κ(Π) = 1. As the past state becomes a weaker instrument, κ(Π) > 1. Thus, if the confounding affects multiple timesteps, we would expect κ(Π) to grow as one needs to reach further back in time to find a valid instrument, leading to a looser performance bound. We investigate the effect of the length of confounding on the ill-posedness of the problem empirically in Sec. 6.

heading: 5.2 ENDOGENOUS NOISE
text: Endogenous noise is present only in the expert demonstrations and not applied during learner rollouts. Thus, in contrast to the exogenous setting, we do not need to eliminate the effect of the confounder to perform as well as the expert. Instead, we hope to effectively reduce our uncertainty over the confounder (e.g. the state of the traffic light). We begin by defining the following policies:
∀s ∈ supp(dπE ), πBC(a|s) = dπE (s, a)/dπE (s), πIV (a|s) = p(a|do(s)), (18) where supp denotes support. We prove the following results under endog. noise in Appendix A:
Lemma 1. There exist MDPs for which πE , πBC , and πIV have different trajectory distributions. Lemma 2. If reward r is a function of state and action only, J(πE) = J(πBC) always, while there exist MDPs for which J(πE) > J(πIV ).
Lemma 3. If reward r ∈ {S × A × U → R} (i.e. the reward additionally depends on the confounder), then there exist MDPs for which J(πE) > J(π) ∀π ∈ {S → ∆(A)}.
One take-away from these lemmas is the fundamental difficulty of producing a value equivalent policy to the expert’s under endogenous noise, a result that was concurrently derived via a graphical condition by Kumor et al. (2021) (Defn. 2.3). Consider, for example, an expert driver that stops at an intersection when a traffic light is red. If the learner does not see this light, there is no way for them to ensure they match the behavior of such an expert. However, in the special case where the reward function does not directly depend on the confounder (i.e. eliminating the natural reward function that penalizes the learner for not obeying the traffic light), πBC is value equivalent to the expert, while, perhaps counter-intuitively, causally consistent πIV is not. The value difference is because πIV marginalizes out ut−1 by sampling from P (ut−1) while πBC samples from P (ut−1|st) (see proof of Lemma 1 in Appendix A). πBC is therefore better able to estimate the value of the confounder by utilizing the information in the current state, which is advantageous in the endogenous setting.
5.3 WITH A SIMULATOR: DOUBIL
Algorithm 1 DoubIL Input: Dataset DE of expert trajectories, Policy class Π, Simulator T̂ Output: Trained policy π2 π1 = arg minπ∈Π Es,a∼DE [− log π(a|s)] {Train preliminary policy via moment-matching.} DIV = {(T̂ (s, π1(s)), a′)|∀(s, a′) ∈ DE} {Pass π1’s actions through simulator.} π2 = arg minπ∈Π Es,a∼DIV [(a− π(s))2] {Train final policy on new dataset and output.}
Algorithm 1 can be seen as a variation of generative modeling approach of Sec. 3 and Hartford et al. (2017) where one leverages knowledge of one factor of the P (X|z) distribution and just learns the other factor. Via the Markov assumption, we can factorize P (X|z) = P (S′|s) = ∑a∈A P (a|s)T (s, a). Assuming access to a simulator T̂ that closely approximates the true transition dynamics, we can instead focus on learning the P (a|s) component: the standard imitation learning task. Notably, this first-stage policy is biased as it includes the effect of the confounder: P (a|s) = P (U + πE(s)|s). However, when we use it to simulate transitions, the next states that are produced no longer have the
particular instantiation of the confounder present in the recorded dataset’s next actions. Using a tilde to denote a fresh draw from a distribution, simulated states are drawn from
s̃t ∼ T̂ (st−1, π1(st−1)) (19) while the observed next actions are drawn from
at ∼ πE(T (st−1, πE(st−1) + ut−1 + ut−2)) + ut−1 + ut. (20)
Notice that there are no shared noise terms. This allows us to apply standard imitation learning to this new dataset of (s̃t, at) to learn a causally consistent policy. The two applications of imitation learning lead us to term this algorithm DoubIL. We can translate the guarantee of Theorem 1 to our factored context: Lemma 4. Assume we learn a π1(s) s.t.
max π∈Π Est−1 [ (Est∼T̂ (st−1,π1(st−1))[π(st)]− Est∼P (st|st−1)[π(st)]) 2 ] ≤ δ
Then, optimizing the second-stage MSE to corresponds to recovering a π2 s.t. PRMSE(π2) = √
Es∼dπE [E[π2(s ′)− πE(s′)|s]2] ≤
√ δ + √ .
We prove this lemma in Appendix A. Combining this lemma with Theorem 3 allows one to derive a performance bound of J(πE) − J(π) ≤ cκ(Π)( √ δ + √ )T 2 under exogenous noise. We note that one could simply learn the mapping P (s′|s) but this can be far less sample efficient than merely learning a policy when |A| ≤ |S|, as is often true in practice.
5.4 WITHOUT STATE RE-SAMPLING: RESIDUIL
Algorithm 2 ResiduIL Input: Dataset DE of expert trajectories, Policy class Π, Discriminator class F , Learning rate η Output: Trained policy π Set π ∈ Π, f ∈ F , g̃π = 0, g̃f = 0 while π not satisfactory do L(π, f) = E(s,s′,a′)∼DE [2(a′ − π(s′))f(s)− f(s)2] {Payoff of zero-sum game.} gπ = ∇πL(π, f), gf = ∇fL(π, f) {Perform Optimistic Mirror Descent.} π ← π − η(2gπ − g̃π) f ← f + η(2gf − g̃f ) g̃π ← gπ , g̃f ← gf
end while
Algorithm 2 is the direct application of the game-theoretic approach of Sec. 3 and Dikkala et al. (2020) to imitation learning. We term it ResiduIL because the adversary attempts to predict the residual between the learner and the expert’s actions while the learner attempts to minimize this residual. Notably, this algorithm can be run completely offline (i.e. without access to a simulator). We use the Optimistic Mirror Descent approach of Syrgkanis et al. (2015) to find approximate Nash equilibria in our experiments. Once again, we can extend our past results to the IL setting: Lemma 5. An -approximate equilibrium for the policy player corresponds to recovering a policy π s.t PRMSE(π) ≤ √ .
This lemma dovetails with Theorem 3 to prove that J(πE)− J(π) ≤ cκ(Π) √ T 2 under exogenous noise (Appendix A).

heading: 6 EXPERIMENTS
text: We test DoubIL and ResiduIL on a slightly modified version of the OpenAI Gym (Brockman et al., 2016) LunarLander-v2 environment against a behavioral cloning baseline. We generate
demonstrations by simulating rollouts of an expert policy trained via PPO (Schulman et al., 2017), adding fresh Gaussian noise to the expert’s action as well as cached noise from the last timestep. The latter noise is the confounder. See Appendix B for full parameters. We judge policy quality by computing the MSE between the output of a deconfounded expert query and a learner’s proposed actions on states from expert rollouts. We see that both of our methods are able to more closely match E[a|do(s)] than behavioral cloning, especially in the low-data regime (Fig. 6, left). We also measure the MSE on states from deconfounded expert rollouts – while there are no clear guarantees on this state distribution, we see that our methods generalize better than BC empirically (Fig. 6, middle). One might wonder how, given a dataset of expert demonstrations, one detects whether there is unobserved confounding in the data. We can answer this question by comparing the results of behavioral cloning and either of our above algorithms. We prove the following in Appendix A: Lemma 6. Assume πBC(s) = E[a|s] and πIV (s) = E[a|do(s)]. Then, E[u|s] = πBC(s)−πIV (s).
The implication of this lemma is that comparing the outputs of IVR-based procedures to behavioral cloning can help us detect causal confounding – if they greatly differ with a sufficiently sized dataset, there is likely an unobserved confounding effect in our data. Moreover, the states where they differ represent the parts of the state space where the influence of the confounder is highest. Fig. 6 right is an empirical example of how the test of Lemma 6 can be used to identify areas of the state space where the effect of the confounder is especially strong (e.g. the center).
For linear problems, we can bound κ(Π) (the measure of illposedness) via an eigenvalue ratio (Dikkala et al., 2020). Extending our previous model to include the effect of the last H confounders (at = πE(st) + ∑t j=t−H uj .), we arrive at the bound
κ(Π;H) ≤ √
λmax(E[stsTt ]) λmin(E[E[st|st−H ]E[st|st−H ]T ]) . (21)
We compute this quantity empirically for a linear-quadratic problem with Gaussian confounding and plot results in Fig. 7. As expected, we see that increasing the length of confounding leads to weaker instruments as one has to use states further back in time. Theorem 3 tells us that under exogenous noise, we should expect a weaker instrument to lead to a larger performance gap between the learner and expert. See Appendix B for full experimental setup details.

heading: 7 CONCLUSION
text: We present a model that captures confounding in imitation learning and derive two algorithms, DoubIL and ResiduIL, that are able to utilize history as an instrument to mitigate the effects of unobserved confounders. We prove performance bounds and validate their empirical efficacy under exogenous noise. We also discuss the challenges of learning with endogenous noise.

heading: A PROOFS

heading: A.1 PROOF OF VALIDITY OF INSTRUMENT
text: Proof. We check the instrument conditions in order:
1. Unconfounded Instrument: Z ⊥⊥ U : The Z → X ← U , V → X ← U , and X → Y ← U triples are blocked by standard d-separation rules (Pearl et al., 2016). All paths from Z to U must pass through one of these triples so Z ⊥⊥ U .
2. Exclusion: Z ⊥⊥ Y |X,U : The Z → X → Y , X ← U → Y , and V → X → Y triples are blocked by standard d-separation rules. All paths from Z to Y must pass through one of these triples so Z ⊥⊥ Y |X,U .
3. Relevance: Z 6⊥⊥ X: There is a Z → X edge, which is assumed to be non-degenerate.
Thus, Z is a valid instrument for determining the causal relationship between X and Y .

heading: A.2 PROOF OF THEOREM 1
text: Proof. We simplify notation for clarity in our proof. Consider two vectors of the same dimension, a and b. Assume that ∑N i a 2 i ≤ and ∑N i b 2 i ≤ δ. This implies that ‖a‖2 ≤ √ and ‖b‖2 ≤√
δ. Then, by the triangle inequality, ‖a− b‖2 ≤ ‖a‖2 + ‖b‖2 ≤ √ + √ δ. Setting ai =√ P (z)(E[Y |z]− Ex̂∼g(z)[ĥ(x̂)]) and bi = √ P (z)(Ex̂∼g(z)[ĥ(x̂)]− E[ĥ(x)|z]) proves that
max ĥ∈H
EZ [(Ex∼g(z)[ĥ(x)]− Ex∼P (X|z)[ĥ(x)])2] ≤ δ, (22)
Ez[(E[Y |z]− Ex̂∼g(z)[ĥ(x̂)])2] ≤ (23) ⇒ PRMSE(ĥ) = √ Ez[(E[Y |z]− Ex∼P (X|z)[ĥ(x)])2] ≤ √ + √ δ (24)

heading: A.3 PROOF OF THEOREM 2
text: Proof. The population version of (11) is min h∈H max f∈F E[2(Y − h(X))f(Z)− f2(Z)] (25)
An -approximate equilibrium is an (ĥ, f̂) pair such that:
max f∈F E[2(Y − ĥ(X))f(Z)− f2(Z)]− 2
(26)
≤ E[2(Y − f̂(X))f̂(Z)− f̂2(Z)] (27) ≤ min h∈H E[2(Y − h(X))f̂(Z)− f̂2(Z)] + 2 (28)
Taking the derivative w.r.t f(z) of the payoff and setting it equal to 0, we arrive at
2P (z)E[Y − ĥ(X)|z]− 2P (z)f(z) = 0⇒ f(z) = E[Y − ĥ(X)|z]. (29) Plugging this back into (49) gives us the inequality
EZ [E[Y − ĥ(X)|z]2]− 2 ≤ min h∈H E[2(Y − h(X))f̂(Z)− f̂2(Z)] + 2 . (30)
Assuming we are in the realizable setting (e.g. h(x) = E[Y |do(x)] ∈ H), minh∈H E[2(Y − h(X))f̂(Z)− f̂2(Z)] ≤ 0. Thus, we can write that:
EZ [E[Y − ĥ(X)|z]2]− 2 ≤ 2 ⇒ PRMSE(ĥ) ≤ √ . (31)
We note that Theorem 2 follows somewhat directly from the main theorems of Dikkala et al. (2020) but that it was not stated in this precise form in their work.

heading: A.4 PROOF OF LEMMA 1
text: Proof. We focus on the first two timesteps of the problem. By construction, p(s0) is the same for all three policies. The following statements follow from standard conditional independence rules (Russell & Norvig, 2002):
πBC(a0|s0) = p(a0|s0) = ∑ u0 P (u0)P (a0|s0, u0), (32)
πIV (a0|s0) = p(a0|do(s0)) = ∑ u0 P (u0)P (a0|do(s0), u0) = ∑ u0 P (u0)P (a0|s0, u0). (33) The last equality follows from the fact s0 has no parents. Thus, when combined with the fact that the transition dynamics P (s1|s0, a0) are the same for all three policies, we arrive at the following equality: pπE (s0, a0, s1) = pπBC (s0, a0, s1) = pπIV (s0, a0, s1) (34) The first difference between the trajectory distributions starts at a1. By definition, the expert chooses actions via πE(a1|s1, u0, u1) = p(a1|s1, u0, u1). (35) while the learners instead follow
πBC(a1|s1) = p(a1|s1) = ∑ u0 ∑ u1 p(u0|s1)p(u1)p(a1|s1, u0, u1), (36)
πIV (a1|s1) = p(a1|do(s1)) = ∑ u0 ∑ u1 p(u0)p(u1)p(a1|do(s1), u0, u1) (37)
= ∑ u0 ∑ u1 p(u0)p(u1)p(a1|s1, u0, u1). (38)
The first line follows from the fact u1 ⊥⊥ u0, s1. The last equality follows from Rule 2 of do-calculus (Pearl et al., 2016). Thus, given the action distributions at the second step are not equal, so long as a1 6⊥⊥ u0 and s1 6⊥⊥ u0, all three policies have different trajectory distributions.

heading: A.5 PROOF OF LEMMA 2
text: Proof. We prove J(πE) = J(πBC) via an application of the Performance Difference Lemma (PDL) (Kakade & Langford, 2002). We note that this is equivalent to the graphical argument used by Kumor et al. (2021) (Defn. 2.3 in their paper).
First, we note that p(s0, a0) is equal for both policies. Assuming that p(st−1, at−1) is equal, p(st) must be equal by the fact the transition dynamics are the same. Then, via the fact that πBC matches the conditional distribution of at|st, p(st, at) must also be equal. Thus, by induction, dπBC = dπE . This means that πBC is defined properly everywhere within it’s own state visitation distribution. We then apply the PDL as follows:
J(πE)− J(πBC) = TEs,a,u∼dπ [QπE (s, a)− Ea′∼p(a′|s,u)[QπE (s, a′)]] (39) = TEs,a∼dπ [QπE (s, a)− Eu[Ea′∼p(a′|s,u)[QπE (s, a′)]]] (40) = TEs,a∼dπ [QπE (s, a)− Eu|s[Ea′∼p(a′|s,u)[QπE (s, a′)]]] (41) = TEs,a∼dπ [QπE (s, a)− Ea′∼p(a′|s)[QπE (s, a′)]] (42) = 0. (43)
The third equality follows from the fact the learner’s actions are independent of the confounder, so under dπBC , P (u|s) = P (u). From the proof of the previous lemma, p(a1|s1) 6= p(a1|do(s1)) in general, so πIV and πE can have different state-action visitation distributions after the first timestep. Therefore, for a two-step problem where a1 6⊥⊥ u0 and s1 6⊥⊥ u0, J(πE)− J(πIV ) = T (Es,a∼dπE [r(s, a)]− Es,a∼dπIV [r(s, a)]) > 0 (44) for reward function
r(s, a) =
{ 1, dπE (s, a) > dπIV (s, a)
0, o.w. . (45)

heading: A.6 PROOF OF LEMMA 3
text: Proof. Let ut be a Rademacher random variable (1 w.p. 12 and −1 otherwise) ∀t ∈ [T ]. Let at|st, ut, ut−1 = ut and there be a single fixed state s that no action can leave. Set r(s, at, ut) = 1[at = ut]. Then, J(πE) = T . Notice that p(+1|s) = p(−1|s) = p(+1|do(s)) = p(−1|do(s)) = 0.5. Thus, J(πE) > J(πIV ) = J(πBC) = T2 , the expected number of correct answers of randomly guessing the outcome of a fair coin T times. Furthermore, notice that T2 is the best any π ∈ Π can do. One can see this by considering the problem with T = 1. If there was a policy π with J(π) > 12 , one would be able to use such a policy to predict the outcome of a fair coin better than the Bayesoptimal classifier for coin-betting (p(heads) = p(tails) = 12 ), violating the fact the Bayes-optimal classifier minimizes Bayes error.

heading: A.7 PROOF OF LEMMA 4
text: Proof. Notice that
max π∈Π Est−1 [(Est∼T̂ (st−1,π1(st−1))[π(st)]− Est∼P (st|st−1)[π(st)]) 2] ≤ δ (46)
can be re-written as
max π∈Π
EZ [(Ex∼g(z)[π(x)]− Ex∼P (X|z)[π(x)])2] ≤ δ. (47)
Thus, the proof of Theorem 4 holds as written.

heading: A.8 PROOF OF LEMMA 5
text: An -approximate equilibrium for the policy player is a π such that
max f∈F
E[2(at−π(st))f(st−1)−f2(st−1)]− 2 ≤ min π∈Π E[2(at−h(st))f̂(st−1)−f̂2(st−1)]+ 2 . (48)
With a change of notation, we can re-write this as:
max f∈F E[2(Y − π(X))f(Z)− f2(Z)]− 2 ≤ min π∈Π E[2(Y − h(X))f̂(Z)− f̂2(Z)] + 2 . (49)
Thus, the proof of Theorem 2 holds as written.

heading: A.9 PROOF OF THEOREM 3
text: Proof. By definition,
PRMSE(π) = √
Es∼dπE [E[a ′ − π(s′)|s]]2 = . (50)
Recall that the measure of ill-posedness of the problem (Dikkala et al., 2020; Chen & Pouzo, 2012) can be defined as
κ(Π) = sup π∈Π
√ Es∼dπE [(πE(s)− π(s))2]√
Es,s′,a′∼dπE [E[a ′ − π(s′)|s]]2
= sup π∈Π RMSE(π) PRMSE(π)
(51)
Directly, RMSE(π) ≤ κ(Π) (52)
We repeat the definition of total variation stability of a distribution P (U):
‖a− b‖2 ≤ δ ⇒ dTV (a+ U, b+ U) ≤ cδ. (53) We proceed by noting that TV-stability implies that ∀s ∈ S,
dTV (π(s) + U, πE(s) + U) ≤ c ‖π(s)− πE(s)‖ (54)
⇒ dTV (π(s) + U, πE(s) + U)2 ≤ c2 ‖π(s)− πE(s)‖2 (55)
⇒ Es∼dπE [dTV (π(s) + U, πE(s) + U) 2] ≤ c2Es∼dπE [‖π(s)− πE(s)‖ 2 ] = c2MSE(π). (56)
By Jensen’s inequality,
Es∼dπE [dTV (π(s)+U, πE(s)+U)] 2 ≤ Es∼dπE [dTV (π(s)+U, πE(s)+U) 2] ≤ c2MSE(π). (57) Taking the square root of both sides, we arrive at
Es∼dπE [dTV (π(s) + U, πE(s) + U)] ≤ c RMSE(π) ≤ cκ(Π) . (58) Lastly, we apply the Performance Difference Lemma of Kakade & Langford (2002) as follows:
J(πE)− J(π) = TEs,a∼dπE [Q π(s, a)− Ea′∼π(s)[Qπ(s, a′)]] (59)
= TEs,a∼dπE [Q π(s, πE(s) + u+ ũ1)− E[Qπ(s, π(s) + u+ ũ2)]] (60) ≤ T 2Es∼dπE [dTV (π(s) + U, πE(s) + U)] (61) ≤ cκ(Π) T 2. (62)
We use the fact that the same u would be added to both the learner and the expert’s actions and that rewards are in the range [−1, 1] in the third step.

heading: A.10 PROOF OF LEMMA 6

heading: Proof.
text: E[at|do(st)] = E[πE(st) + ut + ut−1|do(st)] = πE(st) + E[ut] + E[ut−1] = πE(st) (63) E[at|st] = E[πE(st) + ut + ut−1|st] = πE(st) +E[ut] +E[ut−1|st] = πE(s) +E[ut−1|st] (64)
πBC(s)− πE(s) = E[at|st]− E[at|do(st)] = E[ut−1|st] = E[u|s] (65)

heading: B EXPERIMENT DETAILS

heading: B.1 LUNARLANDER EXPERIMENTS
text: For ease of simulation, we remove the legs from the LunarLander vehicle (the joints connecting them to the main body have a state that is not recorded in the observed state), remove the dispersion noise, and generate trajectories with a fixed ground layout.
For all learned functions, we use two-layer ReLu MLPs with 64 hidden units. We use the Adam optimizer (Kingma & Ba, 2014) for behavioral cloning and DoubIL and use the optimistic variant for ResiduIL. We apply a weight decay of 1e-3 to all. We train all methods for 50k steps.
For computational ease, we only learn the mean of P (a|s) for DoubIL and add fresh standard normal noise on-top of it to simulate drawing actions. For more complex noise models, one would need to use a moment matching algorithm (Swamy et al., 2021) in the first stage.
Importantly, DoubIL suffers from a “double-sample” issue (Baird, 1995) where multiple independent samples of g(z) are required to compute gradients of ĥ. To see this, note that the gradient with respect to h of (10) is
EZ [ (E[Y |z]− Ex̂∼ĝ(z)[ĥ(x̂)])(−Ex̂∼ĝ(z)[ ∂
∂ĥ ĥ(x̂)])
] (66)
Notice that x̂ appears under two separate expectations that are then multiplied together. To get an unbiased estimate of this product, two samples of x̂ are required, one for each expectation. Therefore, it is most correct to use multiple samples from g(z) for each update.
Thus, for implementing the “double samples” for the gradient, we compute E1[a′ − π(s′)|s] and E2[a′ − π(s′)|s] using independent samples. Then, we apply a stop-gradient operator to the former expectation before taking a product between the expectations and averaging over s:
L(π) = Es[!(E1[a′ − π(s′)|s])E2[a′ − π(s′)|s]]. (67) This loss function has the correct gradient as it uses independent samples for computing the two expectations.

heading: B.2 LQG EXPERIMENTS
text: We compute the optimal policy for the following canonical linear system via solving a Discrete-Time Algebraic Ricatti Equation via the standard iterative method:
xt = Axt−1 +But−1 (68)
J(K) = T∑ t xTt Qxt + (Kxt) TRKxt (69)
A = [ 1 ∆T 0 1 ] , B = [ 0.5(∆T )2 ∆T ] , Q = [ 1 0 0 1 ] , R = [0.1] ,∆T = 0.1
This is the dynamics of a “sliding brick on a frozen lake.” We then simulate rollouts of 200 timesteps with ut being drawn i.i.d. from the standard normal distribution. We confound actions with the sum of confounders going H steps back:
at = K ∗st + t∑ j=t−H uj . (70)
We simulate 1000 such rollouts to compute (21) empirically. We calculate E[X|z] = E[st|st−H ] = (A + BK∗)Hst−H analytically instead of via samples due to the small value of the quantity in comparison to the variance of the noise.

Review summaries:
The authors proposed a SCM to model latent confounder in the problem of imitation learning. In particular, two cases of exogenous and endogenous noises are considered. For the instrumental variable, they studied the effect of error in estimation $P(X|z)=g(z)$ on Projected Root Mean Squared Error (PRMSE) where $Z$ is the instrumental variable. They also proposed a game-theoric approach to estimate $h(x)= \mathbb{E}[Y|do(X)=x]$. Moreover, they proposed two algorithms to deal with latent confounders in imitation learning. Experimental results showed the proposed algorithms can perform better with respect to behavior cloning.

This paper attempts to study imitation learning from a causal inference perspective. More specifically, let S be an observed state, A be action and Z be an instrumental variable. The authors propose that one should perform causal imitation learning by learning a policy function that could induce the same interventional distribution P(A|do(Z)).

This paper proposes two causal imitation learning algorithms to address the confounding issue that causes spurious correlations. The method relies on instrumental variable regression to correct for confounding effects. The main idea is to use the state variable from the last time point as instrumental variable for the state-act variables at the current time point in a Markov decision process.