Sequence Model Imitation Learning with Unobserved Contexts
Authors: Gokul Swamy
Sanjiban Choudhury
Drew Bagnell
Steven Wu
Venue: NeurIPS 2022 Accept (2022)
Keywords: imitation learning
causal inference

Abstract: We consider imitation learning problems where the learner's ability to mimic the expert increases throughout the course of an episode as more information is revealed. One example of this is when the expert has access to privileged information: while the learner might not be able to accurately reproduce expert behavior early on in an episode, by considering the entire history of states and actions, they might be able to eventually identify the hidden context and act as the expert would. We prove that on-policy imitation learning algorithms (with or without access to a queryable expert) are better equipped to handle these sorts of asymptotically realizable problems than off-policy methods. This is because on-policy algorithms provably learn to recover from their initially suboptimal actions, while off-policy methods treat their suboptimal past actions as though they came from the expert. This often manifests as a latching behavior: a naive repetition of past actions. We conduct experiments in a toy bandit domain that show that there exist sharp phase transitions of whether off-policy approaches are able to match expert performance asymptotically, in contrast to the uniformly good performance of on-policy approaches. We demonstrate that on several continuous control tasks, on-policy approaches are able to use history to identify the context while off-policy approaches actually perform worse when given access to history.

Sequence Model Imitation Learning with Unobserved Contexts
Gokul Swamy Carnegie Mellon University gswamy@cmu. edu
Sanjiban Choudhury Comell University sanjibanc9cornell.com edu
J. Andrew Bagnell
Zhiwei Steven Wu Carnegie Mellon University zs zstevenvu@cma.cm edu
Aurora Innovation and Carnegie Mellon University dbagnell@rt cmu. edu
Abstract
We consider imitation learning problems where the learner's ability to mimic the expert increases throughout the course of episode as more information is revealed. One example of this when the expert has access to privileged information: while the learner might not be able to accurately reproduce expert behavior early on an episode, by considering the entire history of states and actions, they might be able to eventually identify the hidden context and act the expert would. We prove that on on-policy imitation learning algorithms (with or without access to queryable expert) are better equipped to handle these sorts of asymptotically realizable problems than off-policy methods. This is because on- policy algorithms provably learn recover from their initially suboptimal actions, while off- off-policy methods treat their suboptimal past actions as though they came from the expert. This often manifests as a latching behavior: naive repetition of past actions. We conduct experiments in a toy bandit domain that show that there exist sharp phase transitions of whether off-policy approaches able match expert performance asymptotically, in contrast to the uniformly good performance of on-policy approaches. We demonstrate that on several continuous control tasks, on on-policy approaches are able to use history to identify the context while off off-policy approaches actually perform worse when given access history.
Introduction
An unstated assumption in much of the work in imitation learning (II.) is that the learner and the expert have access the same state information. With powerful enough statistical models, this assumption places us in the realizable setting - i.c. the imitator can actually behave like the expert. In practice however, an expert might have more information than the learner does. For example, an expert policy might be trained in simulation with privileged access to state before being used to supervise learner policy that only has access a subset of features. This recipe has enjoyed success in domains from motion planning with obstacles [Choudhury et al. 2018). to autonomous driving
Chen 2 legged locomotion [Lee et 2020 Kumar al. 200T].
Recent theoretical work has established "no-go" results for successfully imitating an expert that has access to more information [Zhang al. 2020 Kumor et al.] [022T] The core of their arguments that without seeing some feature that influences expert behavior but is not echoed elsewhere in the state, the learner might not be able properly ground the expert actions in the observed state. In causal inference terms, this hidden information acts as an unobserved confounder which prevents identification of the desired causal estimand (the expert action). Despite these results,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

impressive empirical successes have been achieved even when the learner has a more impoverished state representation than the expert.
In this work, we reconcile theory and practice by considering a broad class of problems where the learner's ability to mimic expert actions increases as more observations are revealed. We study the large-horizon limit to tease out what is key to good performance. We find that off-policy approaches (e.g, behavioral cloning) that ignore the resulting covariate shift from initially sub-optimal decisions can lead to poor results, even when there exists a policy that in the large-horizon limit is optimal. We show that for some problem families, there exists a sharp phase transition in problem parameters where off- policy IL shifts between being consistent to having arbitrarily poor performance.
In contrast, show that on on-policy approaches that leverage interaction with the demonstrator [ooss et al. 2010] or take advantage of interaction with the environment (in the style of Inverse Optimal Control [Bagnell, 20155) (Ziehart al.. 2008 Ho and Ermon 2016) are always (i.e. independent of parameters) asymptotically consistent on these problems. We believe this strong separation between on- and off- policy approaches helps explain both the poor performance of behavioral cloning even in regimes with large data and powerful model classes [Spencer et al. [021] Muller et al. 2006
Codevilla et al., 2019 de Haan et al.) 2019. Bansal al. 2018] Kuetler al. 2017 and the success of on-policy methods mentioned above.
We note that, in contrast to the hidden state that is common in real-world problems [Boots et a 2201 I Kumar et al., 2021 Lee et al. 2020], standard benchmarks like the PyBullet suite [Coumans and 2016 are fully observed, enabling off- algorithms like behavioral cloning to match expert performance [Swamy et al. 2021]. Thus, for our experiments, we introduce partial observability to ensure that we are focused on part of what makes imitation learning hard in practice.
We study in detail Contextual Markov Decision Process (CMDPs) [Hallak et al. 2015] that satisfy an asymptotic realizability condition. Intuitively, this means we can expect that proper utilization of history to eventually enable accurate prediction of the context. A key result we show is that for identifiable CMDPs where the learner can recover from mistakes early on in episode, on-policy imitation learning algorithms that operate in the space of histories are able to asymptotically match time-averaged expert value, while off-policy approaches struggle to do so.
More concretely, our work makes three contributions:
1. We show that under appropriate identifiability and recoverability conditions, the context- dependent expert policy becomes asymptotically realizable, enabling on- on-policy imitation learning algorithms to match (or nearly match) time-averaged expert performance.
2. More generally, we show that when longer history allows the learner to get closer to realizing the expert policy, on on-policy methods able to take advantage of this property while off- policy methods are stuck with the consequences of their mistakes early on in an episode. This manifests off-policy methods producing policies that merely repeat previous actions.
3. We conduct experiments in a simplified bandit domain which show that there exist sharp phase transitions terms of when off off-policy imitation learning algorithms match expert performance in contrast to the uniform value-equivalence of the policies produced by on- policy approaches. We also conduct experiments on continuous control tasks that show that on-policy algorithms are able to take advantage of history to correctly identify the context in a way that off- off-policy methods are not.
We begin with discussion of related work.
2 Related Work
One of the fundamental challenges of imitation learning (or any sequential prediction task where the learner consumes some function of its own prior predictions) is the likelihood of significant covariate shift between training-ting -ime data and test test-time observations [Ross and Bagnell 2010]. In short, this happens because the learner might end up in states not seen in the demonstrations and is thus unsure how to act. Early work in this area includes that of Daumé et al. (2099] in the natural language processing and that of Ross et al. (2110) in imitation learning and robotics, both of which come to the preceding conclusion. Recent work by [Spencer et al. (202T) shows that there are actually more than one regime of covariate shift. In the "casy" regime where the expert is realizable, off-policy

---

methods like behavior cloning match expert performance when data and model capacity are large enough. However, in harder regimes where the expert is non-realizable due to model misspecification. off-policy methods compound in error and one must rely on on-policy methods, either those that require an interactive expert [Ross et al., 2010] or an interactive simulator (Ziebart et al.) 2008 Swamy et al. 2021].
One instance of model misspecification of practical interest is when the learner is denied state information that the expert uses. For instance, in self-driving, the human expert might have richer context about the scene than the limited perception system of the car. While the standard solution is to add a history of past states and actions to the model, practitioners have often noted that this leads to a "latching effect" where the learner simply repeats the past action. For example, [Muller et al.]
[2006] note such latching with steering actions. Kuefler et al. [2017), Bansal et al.) [2018] note this with braking actions, and Codevilla et al. [2019] with accelerations. Recent work by Ortega et al. [222] also points out this latching behavior which they term as "self-delusion."
Once one identifies the downstream effect of missing context as covariate shift, a natural question is whether an extension of prior covariate-shift-roburs imitation learning methods to the space of histories would be able learn effectively in partial information settings. Prior work has answered parts of this question. For example, Choudhury et al. (0018) proves that interactive imitation learning over the space of histories converges to the QMDP approximation of the expert's policy [Littnan eet al. 1995]. Recent work Ortega et al. [2021] views these kind of partial information setting through a causal lens Pearl al., 2016], and provides an algorithm (counterfactual teaching) equivalent to the interactive-experr FORWARD algorithm Ross and Bagnell (2010) under log-loss. We build upon these analyses by providing conditions under which such approaches will converge to a policy that is equivalent in value to that of the expert in the presence of unobserved contexts.
Our focus on the contextual MDP (Hallak et al. 2015 is because, as argued by (Zhang et al. 2020 Kumor et al. 2021]. context that is updated throughout the episode and is only reflected for a single step prevents the Tearner from refining its estimates via considering history. Our results apply to settings beyond the CMDP where similar asymptotic realizability property holds. Tennenholtz et al. (2021) consider IL. in contextual MDPs but give the learner access to the confounder at test time and do not consider policies that operate over the space of histories. de Haan et al. (2019) also consider imitation learning from a causal inference perspective but focus on issues of covariate shift (Spencer et al.] 2021]. J, rather than those of missing information. (Swamy et al. [002)] also consider unobserved confounders in IL but focus on correlated action perturbations rather than partial observability.
Wen et al. 2020 2021 2022].
Chuang et al. [2022] propose various offline approaches to mitigating the latching effect (which they term the copycat problem). However, as we prove below, online interaction with the environment is both necessary and sufficient to prevent compounding errors and the associated latching effect. It therefore difficult to provide strong theoretical guarantees for their work or argue that their results in simulation would necessarily transfer to real-world problems.
3 The Latching Effect in Off-Policy Imitation Learning
Consider a finite-horizon Contextual Markov Decision Process (CMDP) parameterized by (S, T,T. T.r, the transition operator. r: S x AA the beginning of each episode, a context is sampled from p(c) and is held fixed until the next reset. Intuitively, there exists a family of reward and transition functions that are indexed by the context for each episode. We use h E H to denote a t-step history: (81, 01,..., St). We see trajectories gener- ated by an expert policy E S > ((A) and search over vare-ng policies π H - A(A). We use II... to refer to the sequence of policies that comprise this time-varying policy, We assume that our policy class II is convex and compact.
I") where S, A. C are the state, action, and context spaces, T : S x A x C + A(S)
+ [-1, is the reward function, and is the horizon. At
We begin with toy example of the latching effect and how it leads to poor policy performance.
Problem 3.1 (Causal Bandit Problem, [Ortega et al., 2021] ). Consider an episodic MDP with K actions (arms) and a single state. At the beginning of each episode, a context e E [K] is chosen uniformly at random and represents the correct arm for that episode. Pulling an arm leads to binary
feedback: + if the arm was correct and otherwise. This feedback is flipped with probability 6ohs E [0, 1]. The learner observes expert demonstrations where at each timestep, the expert plays the
correct arm with probability 1 Eeap [0, 1] and another arm uniformly at random otherwise. The
3

---

Consistency of zotf
Consistency of zeth
Cats 0.3, Geep
0.2
Correet Arm
0.6
0.6
+
0.6
0.6
Coep
02
0.2
0.2 0.6
CouM 0.5
0.4 0.6
500
1000
1.000
2000
Coop
Figure 1: We plot whether the learner's policy has higher probability of making mistakes than the expert (Eeps) after 2000 steps, averaged across 100 trials on instances with K 5. We use red dots to indicate when this is true and green dots otherwise. We see the on on-policy method match expert performance everywhere the problem is identifiable in contrast to the off- policyy method, for which a slight perturbation of a parameter can lead to a drastically different result in terms of tong-term performance, On a particular problem setting, we see the off- aff-policy method pick random arm and repeat it ad infinitum and therefore perform at the level of random chance while the on-policy method is able to match expert performance.
reward function 1 for pulling the correct arm and otherwise. We emphasize that the learner does not observe the rewards, just noisy binary feedback observation after each pull.
As the learner does not observe the correct arm, we are in the partial information setting. However, as one might expect, by pulling all arms enough times and observing the noisy feedback, the learner can narrow down which arm they should pull for the rest of the episode. Note that the learner stays in the same state after each action so they are free to perform this exploration without long-term consequences.
Observation 1: Off-Policy Methods Have Consistency Phase Transitions. In Fig. I we plot, for variety of settings of the problem parameters (Eezp, Cobs) whether the learner makes mistakes with a significantly higher probability than the expert does for an off-policy IL algorithm and an on-policy IL algorithm. We give all learners access to the full history of interactions (i.e. arms pulled and noisy feedback observed). With exactly Cabs = 0.5, the learner gets no information from the observations, preventing any algorithm from learning properly. This means that under this particular setting, the problem instance is not identifiable, a concept we develop further below. In contrast to the uniform consistency of the on-policy approach whenever the problem is identifiable, we see sharp phase transitions in terms of where the off-policy approach is consistent a small change to either problem parameter can lead drastically different result.
Observation 2: Off-Policy Methods Produce Latching Policies. At the first timestep, all learners pick arm uniformly at random they have no information about the context. In the cases where the off-policy approach is inconsistent, it continues to pick this arm ad infinitum as treats its own past actions as though they were the expert's This is what leads to the the rightmost part of Fig. []] even after 2000 timesteps of experience telling the learner that another arm should be pulled. Put differently, the off- oof-co learner collapses its uncertainty over the correct arm too quickly for the negative feedback it receives to push it to a different arm. Concerningly, this effect appears to be extremely sensitive to the parameters of the problem, rendering it difficult to predict and hedge against.
5 success rate seen in
Observation 3: Low Density Ratios Help Off-Policy Methods. Looking at the left side of Fig, natural question might be why, as we increase ceap. the off-policy approach is consistent for a wider spectrum of Cobs values. Observe that we increase cerp. the expert has a higher chance of making a mistake, bringing its trajectory distribution closer to that of the uniform policy and lowering the maximum density ratio between learner and expert trajectory distributions. As established by Spencer et al. (2021]. a low maximum density ratio a sufficient condition for behavioral cloning to be consistent. This experiment appears echo their theoretical results.
Putting together Fig. [ on-policy approaches appear to able to handle hidden context given access to history while off-policy can do so only in way that depends heavily on problem parameters.

---

h1
hg
h
hs
as
@1
(a) n
(b) On On-Policy
(c) Off-Policy
Figure 2: (a): The SCM that corresponds to the generative process for expert trajectories. (b): The SCM corresponds the generative process for learner trajectories in reality, (c): The SCM that corresponds to the generative process that off- off-pooicy algorithms assume intuitivelly it corresponds the expert taking all actions up till the current timestep and then handing off control.
4 A Bayesian Perspective on the Latching Effect
To begin to explain this difference in behavior of on-policy and off-policy algorithms, we consider the structural causal model (SCM) each of these classes of algorithms is implicitly assuming.
4.1 SCMs for Imitation Learning
We observe that expert trajectories of length are generated according to
p(r: A p(c)p(s)) II
(aslc, (s
(1)
while learner trajectories are generated according to
p(T;)) e p(c)p(s1)
II (a
(2)
We use 7 ~ R and T ~ π to denote T-step trajectories sampled according to the above distributions.
We detine our value and Q functions as usual: (*((s= = |E> 1 r(se, av)], )]. (s)
B Ex a()), Lastly, let performance be ((T) E E+ DE r(s,, at)].
The key difference between on-policy and off-policy imitation learning algorithms is the difference between the center and right SCMs of Fig. - On-policy algorithms assume the data they have seen thus far is generated by executing learner π (b) while off-policy algorithms assume it is generated by executing the expert policy x (c). The off-policy approximation is what leads to the latching behavior observed empirically; even if the first action was chosen at random, by treating it as though it was produced by the expert T. (who sees the context e and therefore picks actions that are correlated across time), the learner is likely to continue to repeat the past action. This is also what we observe empirically in the causal bandit problem the cases where off off-policy does not work: the learner continues to play the first arm it chose, ignoring the feedback it gets that it is repeatedly making mistake, and only matching expert performance on a K of episodes. We note this gives the off- off-policy learner choice between fire and pyre (in the words of [llot 1942]): they need to use history to narrow down the context but if they do, they can learn a latching policy that performs poorly at test-time.
4.2 Off Policy Methods Have Incorrect Context Posterior
Another way of seeing this point is by considering what the posterior over the confounder would be under samples from each of these SCMs. If the learner was able accurately pin down the correct arm, they would be able to easily reproduce the expert policy. Thus, we can focus on correct-arm identification via Bayes Rule. Assuming uniform prior over contexts,
p(clha) p(c, hz).
(3)
5

---

Under the off-policy graphical model, p(c, h4) x <)r;==)): the probability of a history h1 under the expert's distribution (Fig. 2 (a)). Expanding terms, we arrive the following expression Proposition 4.1. The off-policy posterior over contexts is
(o h4) p();;=") p(c)p(s1) II
x
c).
(4)
Notice that for the expert policy, the context directly influences actions conditioning actions when attempting to predict e is correct. We highlight in green the term that encodes this dependence. In contrast, if we assume the learner has access the context except via its influence the history of states, we should instead treat actions as interventions (Pearl et al. 2016) that provide no further information about the context. The on-policy graphical model (Fig. (b)) does just this, allowing us to compute the correct posterior over contexts. Formally, Proposition 4.2. The on-policy posterior over contexts
Poulc, hi) p(h;; d.cld si) p(c)p((1) II T(s+1 a,,c, (5)
where the equality follows from the fact that
(c 1. a1.... (1....) 1)..
(6)
and the standard dol)-clls rules (Pearl et al. 2016). Intuitively, we are leveraging the fact that the learner's s actions have all their dependence on the context mediated through the history of states to ignore them in our posterior calculation. Notice that this expression matches the off off-policy posterior except for the term in green: because the on-policy learner knows that the actions in the history were not produced by the expert, does not weight them the expert's probability of playing them in its posterior update. Graphically, as far as the posterior over the context is concerned, on-policy approaches correspond to the SCM in Fig. left.
Learner picks randomly
hn
Off-Pulicy, 1=1
Off-Policy, I=2
0.33
0.33
C C2 C2
C C2 C2
Figure 3: Left: The SCM for CMDP that treats actions interventions that provide useful information about the context. This SCM what the on-policy learner uses when performing posterior updates. Right: By treating its own actions as though they came from the expert, an off-policy learner's posterior collapses too quickly on an incorrect context, causing latching.
By ignoring its own incorrect actions early on, the on-policy learner doesn't 't over-index on them and come false conclusion as what the value the context is, as illustrated in Fig. [3] right. We'r ve already seen evidence of how the addition or removal of the green term can lead to markedly different results: the learners we used to generate Fig. had policies given by
n: off (at (1x) = Σ (c)lbc st),
CEC
and
TH (a, (b) Σ ((accc))) (aclc,s)).
(8)
GEC
Note that these policies are exactly equivalent except for the green term in the posterior of the off-policy off yet respond quite differently as the parameters of the problem are changed. Also note that Pon (c)ht) requires interaction with the environment to evaluate, while Poft Pon(cc// (c//,) does not.

---

A Moment-Matching Solution to the Latching Effect
We turn attention generalizing this argument beyond Bayesian learners, including to those that match sufficient statistics of expert behavior moments rather than maintaining explicit posteriors, and providing value equivalence guarantees for bistory-equipped on-policy learners.
5.1 A Quick Review of Moment-Matching in Imitation Learning
First, as in Swamy al. [201]] we define Foe as the set of on-Q moments, with f E FQe satisfying type signature S x A x C > [-7, T.. Intuitively, Fog spans the set of possible expert Q- Q-functions. We require the actual expert Q-function to be contained: QTE E FQg. We assume that Foz is convex, compact, closed under negation, and finite dimensional. Second, define FQ be the class of off-Q moments (i.e. Vπ E 11. Q E Fe) and satisfy the same function-class assumptions as FQR. Third, let Fr denote the class of reward moments and also satisfy the same function-class assumptions. All f E F, satisfy type signature S x A x + [-1, and we assume that F,,.
Swamy et al. 2021] prove that if one is able to approximately solve a two-player sero-sum moment- matching game between a policy player (that picks from II) and a discriminator (that picks from FQr FQ. or F,), one has bound on the performance difference between the learner and the expert. Depending on which class the discriminator selects from, one ends up with a different bound. For example, if one solves the game with the following payoff and f E Fr to an e-approximate Nash equilibrium,
U(T
f(s, at c)]
E TNI
2 (st,
T~R
one has a guarantee that B) ((T) < eT. Unfortunately, directly solving such game is not possible in the hidden context setting as we do not see the contexts and therefore cannot evaluate the moment functions. We turn our attention adapting moment manchhng to the contextual setting.
5.2 Moment-Matching with Unobserved Contexts
For each moment class, we assume the existence of an observable moment class that operates over the space of histories (i.e. H A IR) and has members that eventually produce outputs close to that of their context-dependent counterparts. In math,
Assumption 5.1 (Asymptotic On-Q Moment Identifiability)
vʃ Fog, Ve C, C, Foz s.l. lim sup Br.s,ol/(sT,a,c) a)) =0 (10) T-x rETlu>=)) aeA
Analogous conditions can be defined for F, and Fq- giving F, and Fo. We note that these condi- tions are asymptotic in nature we use 5(t) to refer to the finite-horizon expected difference between the observable and context-dependent moments. We И to denote the moment recoverability constant, which bounds how much total cost is incurred for the expert to recover from an arbitrary mistake (Swamy et al. 202T]
H
sup f(s,a,c) Eg (fo)
(11)
aEA..E &EC,
For problems where the expert is able effectively correct learner mistakes, this quantity can be significantly smaller than the horizon. Define F.n ( FQz) and Faft (ff2TT Fo) be saaled-dow versions of the observable moments such that their range is [-1, 1). We can now define our moment-matching errors:
Con (1) sup Ey-z Br-z[f(Me, at) Ba (er JeFon
(12)
'The astute reader might notice that we need access to context to simulate learner rollouts as context also affects the transition model. Thus, as long as one can simulate, one can do standard moment matching in the space of context depeneede moments. We write things in history-space to also handle the real-world setting where contexts always unavailable.
moment-matching
7

---

Cofr(t) sup
ET (f ar)- En (h
(13)
feFoa
Frew (t) sup Brow (he az)l Ei lf at)] jEA,
(14)
2021 fron (1) governs the performance of on-Q algorithms like DAgger [oss et al. 2010 (ofr(f (f) the performance of off-Q algorithms like behavioral cloning [Pomerlcau 1989 and Crew (t) the performance of reward- matching algorithms like MaxEnt IRL [Ziebart et al.
As argued by Swamy et al.
2008 and GAIL (Ho and Ermon 2016]. With these definitions laid out, we can now prove how well each class of algorithms handles unobserved contexts.
5.3
Asymptotic Realizability in Imitation Learning
For some partial information problems, the use of history coupled with on-policy feedback might allow the learner to eventually match expert performance. This is an example of more general phenomenon we term asymptotic realizability (AR), in which the learner is able to perform as well as the expert does with high probability after observing an arbitrary history of some length. We begin by defining the average imitation gap or AIG for short.
Definition 5.2 (AIG(z, T)).
T
T
Σ T
r(s) an. c)l - Eroo T
Σ
r( ae c)].
(15)
We now define our performance target in AR problems. Definition 5.3 (Asymptotic Value Equivalence (AVE)). We say that policy æ is asymptotically value-equivalent (AVE) when the following condition holds true:
lim AIG( T) =0. 0.
(16)
Intuitively, this condition means that the learner performs as well as the expert does on average, given enough time. Put differently, we do not penalize the learner for initial mistakes as long as they are able to learn enough from them to match expert performance. We will proceed by studying the AIG properties of on-policy and off- off- policy imitation learning algorithms.
We are now ready state our main result:
Theorem 5.4 (AVE of IL Algorithms). Define lim sup, Con
(on (t) = Can (co). limy ES coff coft(t) + Suft (1) Eor(c0), (oo), and lim sup,++00 frew (1) crew (oO). For all (C)MDPs and n lim ATG(TT, 7) S con (oo) T
(17)
lim AIG(T, 7) - 2off (00), T-x
(18)
lim AIG(T, S frew (oo).
(19)
T
In words, if either an on-Q geward-matching learner is able to achieve 0 moment matching error asymptotically, they will achieve the same average value as the expert. Even if they are unable to do so, the AIG will be bounded by a constant. In contrast, the result for off-policy algorithms is much weaker. Notice that instead of taking a lim sup which, roughly speaking, captures the asymptotic error, the off- off-policy bound is in terms of the sum of errors, which factors in errors made early on. This result indicates that an off- learner that makes mistakes carly on in the episode (as is likely for contextual problems) might be unable to eventually match expert performance, even when the problem is recoverable. We prove that there exist certain problems for which this bound is tight.
lim
Theorem 5.5 (Off-Policy AVE Lower Bound). There exist CMDPs and s.f. lim sup; foff (t) = for which
lim AIG(T, T) 2 (oo).
(00)
T-200
8

---

RalChectaBullleBee
Anthulettiovv
20
10-
100-
LAggsE Sigget
Figure 4: We use the suffix SEQ to refer to models that have access to history (of length for all experiments). Standard errors computed across 4 runs. Left: We consider modification of the HalfCheetah task where the goal is for the agent to run at a particular velocity. The expert sees this velocity while the learner observes
indicator of whether their current velocity is above or below the target, achieving F(T=) = 560. We see that adding history to BC actually reduces the performance of the learned policies, in contrast, DAgger. We also that DAgger-SED eventually out-perform DAgger in terms moment-matching error. Right: We consider a modification of the Ant task where the target velocity is only revealed to the learner at f 200. The expert achieves (TTg) = 300. We again see using sequence models harms BC performance while reducing DAgger mnoment-matchinn error. While all methods drop in error at 200, the drop particularly large for the on- on-policy methods, indicating that they are better able to manage uncertainty over the context.
In words, this theorem says that for certain problems, even if an aff-policy learner can drive down error asymptotically, they might be doomed as far as AVE because of mistakes made early on.
We prove these results in Appendix [ To come full circle, causal bandit problem) that satisfy the asymptotic moment identifiability conditions along with an asymptotic realizability condition the policy class enable the learner match expert performance:
argue that CMDPs (including
Assumption 5.6 (Asymptotic Realizability). Asymptotic Moment Identifiability holds and 3π E II s.t. lim, con (1) 0, lim coft (I) O, and lim;- <rew (1) = O.
Note this assumption is weaker than standard realizability assumption it is saying that along certain moments of interest, we can asymptotically match the expert. Plugging in this assumption into Theorem 5.4 tells us that on such problems, an on-policy learner will be able to achieve AVE.
We now turn our attention to efficiently computing such a policy. We prove that by solving an approximate equilibrium computation game over the space of history-based policies and the space of observable moments (which can be done efficiently with no-regret algorithms, [Freund and Schapire 1997)), one can find policy that achieves a low AIG.
Theorem 5.7. For any contextual MDP and policy class that satisfies Asymptotic Realizability, let be an e-upproximate Nash equilibrium strategy for the infinite horizon reward-matching or on- Q-matching game. Then, we know that lim AIG(T,T) T) S e or limq AIG(T, T) I)= S He.
In short, by solving on-policy noment--mtching problem over policies that have access history, we have strong guarantees of matching expert performance on asymptotically realizable problems. We re-iterate that we have such guarantees for off- off-policy algorithms. We also note that causal bandit problem satisfies these assumptions, providing theoretical justification for our results.
Corollary 5.8. There exists a singleton observable moment class such that the Causal Bandit Problem satisfies Asymptotic Realizabiliry, implying that the iterates produced by an on-policy moment matching algorithm will achieve AVE.
Putting it all together, for asymptotically realizable problems, on-policy imitation learning algorithms have stronger guarantees than their off off-policy counterparts with respect asymptotic value equiv- alence. If contextual MDP satisfies these conditions (like with our Causal Bandit Problem), the preceding results apply. We see that our theory matches our experiments: on-policy algorithms appear to work on all identifiable instances of the causal bandit problems, while off-policy algorithms have much weaker performance. We now turn our attention to more complex CMDPs that satisfy our assumptions to further validate our theory empirically.

---

Experiments
We conduct experiments in CMDP extension of the standard PyBullet tasks Coumans and Bai [2016] that is inspired by the multi-task reinforcement learning setups of Finn et al. [2017]. In these tasks, the agent is rewarded for running at a particular velocity that is randomly sampled the beginning of each episode. We train expert policies that have access to this privileged information. We compare two algorithms: the off- off-policy behavioral cloning (BC) [Pomerleau) [989] and the on-policy DAgger (DAgger) [Ross et al.) 2010] that either have access to the immediate state or the last five timesteps of history (for which we use the suffix -SEQ).
In the bar plots of Fig. 4 we see that without access to history, BC performs poorly. As our theory predicts, when we equip the BC learner with history, we actually see it perform worse on average, exhibiting the latching behavior that has been observed repeatedly in practice, In contrast, we see that equipping our on on-policy learner with access the last few observations and actions does not lead to sharp decline in terms of performance. We use MSE as a surrogate for moment- matching error. We see that on both environments, on-policy methods are far better matching expert actions on their own rollout distribution. We also see that with enough time, DAgger- is able to predict actions better than DAgger (lower con ( (1000)). Putting together these observations, appears as though on-policy methods with access to history are the most robust against partial information, agreeing with our theory. We release our code wtthtts::/// thub. com/ /ttpm//wwwww////eeee wttp://eeeeeeeeeeeeeeeeeeeeeeeee peppueencemodee._.eee
moment-matching
Conclusion
We study asymptotically realizable imitation learning problems where the learner's ability mimic the expert increases over the timesteps of the problem. We find that under identifiability and recoverability assumptions, on-policy algorithms able to match time-averaged expert value, in contrast to aff-policy algorithms which might pay for their early mistakes for the rest the horizon. We demonstrate that empirically, off-policy algorithms are not able to take advantage of history to uncover missing information. We believe our results point towards a unified explanation of both empirical successes and failures.
8
Acknowledgments
ZSW is supported in part by the NSF FAI Award #1939606. Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, an Okawa Foundation Research Grant, and Mozilla Research Grant. GS is supported computationally by GPU award from NVIDIA and emotionally by his family and friends.
10

---

References
J Andrew Bagnell. An invitation to imitation. Technical report, Carnegic-Mellon Univ Pittsburgh Pa Robotics Inst, 2015.
Mayank Bansal, Alex Krizhevsky, and Abhijit S. Ogale. Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst. CoRR, abs/1812.03079, 2018. htthhttpp///xxiv org/
abs b 1812. 03079.
Byron Boots, Sajid M Siddiqi, and Geoffrey J Gordon. Closing the learning-planning loop with predictive state representations. The International Journal of Robotics Research, 30(7):954-966, 2011.
Dian Chen, Brady Zhou, Vladlen Koltun, and Philipp Krähenbühl. Learning by cheating, 2019. URL
https://arxiv.orrg org. www.aa////.. 12294
Sanjiban Choudhury, Mohak Bhardwaj, Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sebastian Scherer, and Debadeepta Dey. Data-driven planning via imitation learning. The International
Journal of Robotics Research, 37(13-144:1632-1665 2018.
Chia-Chi Chuang, Donglin Yang, Chuan Wen, and Yang Gao. Resolving copycat problems in visual imitation learning via residual action prediction. In European Conference on Computer Vision, pages 392-409. Springer, 2022.
Felipe Codevilla, Eder Santana, Antonio M. López, and Adrien Gaidon. Exploring the limitations of behavior cloning for autonomous driving. CoRR, 0oos/1904.089800 2019. URL TRRLhttp:// battp://arre /arxxvv org/abs ttab//9944 08980
Erwin Coumans and Yunfei Bai. Pybullet, python module for physics simulation for games, robotics and machine learning. 2016.
Hal Daumé, John Langford, and Daniel Marcu, Search-based structured prediction. Machine learning, 75(3):297-325, 2009.
Pim de Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. Advances in Neural Information Processing Systems, 1698-11997, 2019.
T.S. Eliot. Little gidding, 1942.
http://wwwwbbaaaacc/c//////aaaaa 35200//dlt//sallllliilleggggggg html
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agmostic meta-learning for fast adaptation of deep networks, 2017. httpppp://aaaii...rr/////////... 03400
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 199-139, 1997.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018. URL https
//arxiv.org/ http/oorgg/abb//111002222
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes, 2015. URL
https://arxiv. org www.oo/gg///....../.00 0225902299990
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advances in neural
information processing systems, 29, 2016.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412,6900 2014.
Alex Kuefler, Jeremy Morton, Tim Wheeler, and Mykel Kochenderfer. Imitating driver behavior with generative adversarial networks. In 2017 IEEE Intelligent Vehicles Symposium (IV), pages 204-211. IEEE, 2017.

---

Ashish Kumar, Zipeng Fu, Deepak Pathak, and Jitendra Malik. Rma: Rapid motor adaptation for legged robots, 2021. httpss:///axx http://rrxx...rggbsasss/as// http///b//201... 040044
Daniel Kumor, Junzhe Zhang, and Elias Bareinboim. Sequential causal imitation learning with unobserved confounders. Advances in Neural Information Processing Systems, 34, 2021.
Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladlen Koltun, and Marco Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47):eabc5986, 2020.
Michael L Littman, Anthony R Cassandra, and Leslie Pack Kaelbling. Learning policies for partially observable environments: Scaling up. In Machine Learning Proceedings 1995, pages 362-370. Elsevier, 1995.
Urs Muller, Jan Ben, Eric Cosatto, Beat Flepp, and Yann Cun. Off-road obstacle avoidance through end-to-end learning. In Advances in neural information processing systems, pages 739-746. Citeseer, 2006.
Pedro A Ortega, Markus Kunesch, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Joel Veness, Jonas Buchli, Jonas Degrave, Bilal Piot, Julien Perolat, et al. Shaking the foundations: delusions in sequence models for interaction and control. arXiv preprint arXiv:21 10. 10819, 2021.
Judea Pearl, Madelyn Glymour, and Nicholas Jewell. Causal inference in statistics: A primer, John Wiley & Sons, 2016.
Dean A Pomerlcau. Alvinn: An autonomous land vehicle in a neural network. 1989.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
Stephane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning, 2010. URL httptttttataii..oortt org/ hasg//bs//oo 1011
0686
Jonathan Spencer, Sanjiban Choudhury, Arun Venkatraman, Brian Ziebart, and J. Andrew Bagnell. Feedback in imitation learning: The three regimes of covariate shift, 2021. URL htttts:///axtti org/abs/ 2102 02872.
Gokul Swamy, Sanjiban Choudhury, Andrew Bagnell, and Steven Wu. Of moments and matching: A game-theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pages 10022-10000 10032. PMLR, 2021.
Gokul Swamy, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Causal imitation learning under temporally correlated noise. In International Conference Machine Learning, pages 20877-20890. PMLR, 2022.
Guy Tennenholtz, Assaf Hallak, Gal Dalal, Shie Mannor, Gal Chechik, and Uri Shalit. On co- variate shift of latent confounders in imitation and reinforcement learning. arXiv preprint arXiv:2 11.00000555 10.06539, 2021.
Chuan Wen, Jierui Lin, Trevor Darrell, Dinesh Jayaraman, and Yang Gao. Fighting copycat agents in behavioral cloning from observation histories. Advances in Neural Information Processing Systems, 33:2564-2555 2575, 2020.
Chuan Wen, Jierui Lin, Jianing Qian, Yang Gao, and Dinesh Jayaraman. Keyframe-focused visual imitation learning. arXiv preprint PrXiv:21066004453 2021.
Chuan Wen, Jianing Qian, Jierui Lin, Jiaye Teng. Dinesh Jayaraman, and Yang Gao. Fighting fire with fire: avoiding dnn shortcuts through priming. In International Conference on Machine Learning. pages 23723-23750. PMIR, 2022.
Junzhe Zhang, Daniel Kumor, and Elias Bareinboim. Causal imitation learning with unobserved confounders. Advances in neural information processing systems, 33: 13:12223-,, 2020.
Brian 7iebart, Andrew I. Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL. USA. 2008.
12


Reviews:
[{"review_id": "tIuWieIE8_y", "reviewer": "Reviewer_Pth8", "summary": "In this paper, the authors study imitation learning in contextual Markov decision processes (CMDPs). Three different frameworks, off-policy, online and interactive, are considered. The authors inspect the differences among the frameworks with structural causal models to show the issue of off-policy methods, such as behavioral cloning, Theoretical analyses for performance bounds are provided as well as a short empirical evaluation.", "questions": "1. Line 177: Bayes rule implies that $p(c|h_t) = p(c, h_t) / p(h_t)$. $p(h_t) = \\sum_c p(h_t|c)p(c)$. Even with a uniform prior over contexts, $p(h_t)$ will not have a uniform distribution. By writing equation (3), $p(c|h_t) \\propto p(c, h_t)$, the authors imply we could ignore $p(h_t)$. Am I missing something here?\n\n\n2. Line 185: in equation (6), $\\mathcal{G}$ is not defined.\n\n\n3. Line 222: I didn’t understand what “$\\mathcal{F}_{Q_E}$ spans the set of possible expert Q-functions” means. Given an expert policy $\\pi_E$, shouldn’t there just be a corresponding Q function $Q^{\\pi_E}$?\n\n\n4. In section 4, can the authors provide what the expert’s performance is, i.e., $J(\\pi_E)$? Is there a performance gap in the DAgger methods?\n", "limitations": "The authors had an adequate discussion on the limitation. I think analyzing the finite-sample setting will be very interesting.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: I found the novelty of this paper to be limited. The main difference from the work by Swamy et al. is the introduction of contexts in MDPs. However, the section (section 3.2) connecting CMDP with structural causal models needs improvement. I am not an expert in causal learning, but after attempting to read this section multiple times, I still could not understand what the connection is. \n\nIn terms of the theoretical results, they largely mirror those in Swamy et al. as well. In fact, the inclusion of the context doesn’t introduce anything new in the analysis. So I didn’t see much novelty here either. \n\nFinally, the CMDP-specific result, Theorem 3.8, is interesting, but due to the strong assumption, Assumption 3.6, the value of the theorem is limited. \n\nOverall, studying performance gap bounds in CMDP is interesting, but the results in the paper is not novel enough.\n\nQuality and clarity: I think the paper needs a significant rewrite to improve its quality and clarity. Many important details are left out which makes the paper confusing to read.\n\n1. In the bandit example in section 3.1, the authors could explain in more detail what applying DAgger in a bandit setting looks like. Moreover, it is unclear what form the policy is, is it a linear model, a tabular agent, or something else? The appendix B.1 failed to answer these basic questions as well.\n\n2. Section 3.2 assumes the reader is familiar with causal learning, such as the part from line 184 - 186. I think many in the imitation learning community will appreciate relevant concepts explained as preliminary before the main message. The same goes for the use of structural causal models (Figures 2 and 3), how does one interpret the color and direction of an arrow?\n\n3. I list some technical questions in the next section as well, which could improve the clarity of the paper.\n\nSignificance: I think the topic is relevant to the community but the results in the paper is not significant to clear the bar for NeurIPS.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mX-P5hF4td5", "reviewer": "Reviewer_GRay", "summary": "The paper discusses the performance bound of on-policy and off-policy imitation learners and the conditions for the learners to achieve expert performance. The theoretical results show that on-policy learners have stronger guarantees than off-policy learners. Experimental results also support the conclusion.", "questions": "For the experiment results in figure 4:\n1. In the left plot, both learners' performances become worse after adding history information. Can we have a more detailed explanation of this?\n2. In the middle plot, the -SEQ methods are all better than their original counterparts, which are opposite to the resuts we see in the left plot. Why is this?\n3. In the middle plot, while the final performance of DAGGER-SEQ is better than DAGGER, it seems to have a worse sample efficiency. Can we have some discussion of this?\n4. For the right plot, can we also have an experiment that shows when BC is able to achieve value equivalance?", "limitations": "Please consider adding more explanation to the questions above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper provides both theoretical proofs and empirical results.\n2. The theoretical results are intuitive and are given with practical conditions for achieving desired performance (Assumption 3.6 and 3.7).\n\nWeaknesses:\nThe experiment results are a bit weak and incomplete. Some of the results are lack of explaination.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AZd_7aoww2i", "reviewer": "Reviewer_wNyh", "summary": "This paper investigates the feasibility of performing imitation learning in a setting where the contexts (in the sense of Contextual MDPs) are unobserved. They show theoretically that purely offline imitation learning methods in this setting can fail to learn the correct causal policy, due to the unobserved context acting as a kind fo confounder. They show that online imitation learning methods which assume access to a queriable expert or environment can address this problem, and that in cases where the context can be identified from the transitions, and early failures aren't recoverable, then these methods can asymptotically match expert value. They perform several experiments on HalfCheetah where the context defines the target speed (i.e. the reward function), and demonstrate that online IL methods perform better than offline IL methods, as the theory predicts.", "questions": "- L292: We don't know that adding history is leading to latching-style behaviour - it could be because optimisation with an LSTM is harder - how much did you sweep the LSTM HPs and architecture?\n- L294: Shouldn't adding history improve the on-policy learner's performance, and is history is necessary for realisability?\n- Fig 4 left - could you plot the expert's performance here for comparison?\n- Fig 4 mid and right - Could you be more clear how you're calculating the y-axis values?\n- L221: It would be beneficial to redefine F_Q_E, perhaps in appendix, so the paper is self-contained.\n", "limitations": "I think the limitations are sufficiently described in the paper ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I like the paper, and I think it provides some clear and intuitive conditions for when offline IL may fail, and how online IL can address these failures. The paper is clearly written, and the contribution is novel. The well-argued theoretical results, along with the conclusions of the results, are the main strengths of the paper.\n\nI think the main weakness of the paper lies in the lack of experimental validation of the theoretical results. While I don't think this suffices as a weakness to reject the paper, I think it could be substantially improved with more experimental evidence that aligns with the theoretical conclusions.\n\nFor example, performing experiments on multiple environments would improve the robustness of any conclusions drawn from the experiments. Further, the theory would seem to suggest that having access to history makes the task realisable, meaning that the policy should have improved performance, but this isn't the case in the experiments. Experiments with MDPs where you can adjust whether the realisability and identifiability assumptions are satisfied and investigating how that affects the performance of offline and online IL methods would be beneficial.\n\nThe best version of these experiments would be a set of experiments across multiple environments, where it's shown that satisfying the assumptions improves the performance of the online IL algorithms more than it improves the performance of the offline IL algorithms (if they improve at all), and that metrics that the theory predicts to behave in certain ways behave in those way empirically. I realise this is a big ask, and as I said I don't think it's necessary for the paper to be accepted, but it would improve the robustness of the scientific contribution of this paper.\n\nAs a separate point, it would be great to see examples of real-world examples that satisfy the asymptotic identifiability and realisability assumptions, and those that don't, to get a clearer intuition of when we can expect these methods to succeed in practice.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept