Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior
Authors: Adam Block
Ali Jadbabaie
Daniel Pfrommer
Max Simchowitz
Russ Tedrake
Venue: NeurIPS 2023 poster (2023)
Keywords: Imitation Learning
Control
Diffusion Models
Optimal Transport
TL;DR: We provide theoretical guarantees for imitating potentially multi-modal expert demonstrations.

Abstract: We propose a theoretical framework for studying behavior cloning of complex expert demonstrations using generative modeling.
Our framework invokes low-level controllers - either learned or implicit in position-command control - to stabilize imitation around expert demonstrations. We show that with (a) a suitable low-level stability guarantee and (b) a powerful enough generative model as our imitation learner,  pure supervised behavior cloning can generate trajectories matching the per-time step distribution of essentially arbitrary expert trajectories in an optimal transport cost. Our analysis relies on a stochastic continuity property of the learned policy we call "total variation continuity" (TVC). We then show that TVC can be ensured with minimal degradation of accuracy by combining a popular data-augmentation regimen with a novel algorithmic trick: adding augmentation noise at execution time. We instantiate our guarantees for policies parameterized by diffusion models and prove that if the learner accurately estimates the score of the (noise-augmented) expert policy, then the distribution of imitator trajectories is close to the demonstrator distribution in a natural optimal transport distance. Our analysis constructs intricate couplings between noise-augmented trajectories, a technique that may be of independent interest. We conclude by empirically validating our algorithmic recommendations, and discussing implications for future research directions for better behavior cloning with generative modeling.

Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior
Adam Block MIT Cambridge, MA ablock@mit.edu
Ali Jadbabaie MIT Cambridge, MA
Daniel Pfrommer MIT Cambridge, MA dpfrom@mit.. edu
jadbabai 0mi miit.ee edu
Max Simchowitz MIT Cambridge, MA msimchow@ceail.c wwt.saaaalii.i......m.mmm.mm.met mit.edi
Russ Tedrake MIT Cambridge, MA russtemit.cs edu
Abstract
We propose theoretical framework for studying behavior cloning of complex ex- pert demonstrations using generative modeling. Our framework invokes low-level controllers either learned or implicit in position-command control to stabilize imitation around expert demonstrations. We show that with (a) a suitable low-level stability guarantee and (b) powerful enough generative model our imitation learner, pure supervised behavior cloning can generate trajectories matching the per-time step distribution of essentially arbitrary expert trajectories in an opti- mal transport cost. Our analysis relies on a stochastic continuity property the learned policy call "total variation continuity" (TVC). We then show that TVC can be ensured with minimal degradation of accuracy by combining a popular data-augmentatton regimen with novel algorithmic trick: adding augmentation noise at execution time. We instantiate our guarantees for policies parameterized by diffusion models and prove that if the learner accurately estimates the score of the moosse-uugmented expert policy, then the distribution of imitator trajectories is close the demonstrator distribution in a natural optimal transport distance. Our analysis constructs intricate couplings between noise-augmented trajectories, technique that may be of independent interest. We conclude by empirically val- idating our algorithmic recommendations, and discussing implications for future research directions for better behavior cloning with generative modeling.
1 Introduction
Training dynamic agents from datasets expert examples, known as imitation learning, promises to take advantage of the plentiful demonstrations available in the modern data environment, in an analogous manner to the recent successes of language models conducting unsupervised learning on enormous corpora of text [67, 70]. Imitation learning is especially exciting in robotics, where mass stores pre-recorded demonstrations on Youtube [1] or cheaply collected simulated trajectories [42, 20] can be converted into learned robotic policies.
For imitation learning to be a viable path toward generalist robotic behavior, it needs be able to both represent and execute the complex behaviors exhibited in the demonstrated data. An approach that has shown tremendous promise generative behavior cloning: fitting generative models, such
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Right Mode
Staliication
Seooodhing Aegenntations
Consider demonstration trajectories exhibiting two modes: a "go left" and "go right" mode around an obstacle depicted in red and purple, respectively. To avoid compounding error, we imi- late sequences of simple low-level feedback controllers we call "primitive controllers", not simply raw actions. Intuitively, primitive controllers provide "tubes" around each demonstration trajectory where the system can be stabilized. Depicted in yellow, our data- data-noising procedure described below "fills in the gaps" in the demonstration, switching between modes in well-behaved manner, and whilst allowing the primitive controllers to manage the stabilization.
Figure I:
as diffusion models [2, 19, 33], to expert demonstrations with pure supervised learning. In this paper, we ask: When can generative behavior cloning imitate arbitrarily complex expert behavior?
In this paper, we are interested in how algorithmic choices interface with the dynamics of the agent's 's environment render imitation possible. The key challenge separating imitation learning from vanilla supervised learning is one of compounding error: when the learner executes the trained be- havior in its environment, small mistakes can accumulate into larger ones; this turn may bring the agent to regions of state space not seen during training, leading to larger-still deviations from intended trajectories. Without the strong requirement that the learner can interactively query the expert new states [40, 57). it is well understood that ensuring some form of stability in the imita- tion learning procedure indispensable [68, 27, 50]. While many natural notions of stability exist for simple behaviors, how to enforce stability when imitating more complex behaviors remains an open question. Multi-modal trajectories present key example of this challenge: consider a robot navigating around an obstacle; because there is no difference between navigating around the object to the right and around to the left, the dataset of expert trajectories may include examples of both options. This bifurcation of good trajectories can make it difficult for the agent to effectively choose which direction to go, possibly even causing the robot to oscillate between directions and run into the object. [19]. Moreover, human demonstrators correlate current actions with the past in order to commit to either right or left path, which makes even formulating the idea of an "expert policy" Lastly, bifurcations necessarily incompatible with previous tions of stability derived from classical control theory [68, 27, 50]. this work, we investigate how these strong and often unrealistic assumptions the expert policy be replaced by practical (and often realistic) assumptions on available algorithms.
conceptually challenging
1.1 Contributions.
As in previous work, we formalize behavior cloning in two stages: at train-time, we learn a map from observations to distributions over actions, supervised by (state, action)-pairs from expert demonstra- tions coming from Nexp independent expert trajectories, while test-time, the learned map, or policy, is executed random initial states (distributed identically to initial training states). Follow- ing the schematic existing theoretical analyses of behavior cloning [68, 50, 27], we demonstrate that policy trained by minimizing certain supervised learning objective induces trajectories that approximate those of expert demonstrations. Our work considers a signif- icantly more general setting than past theoretical literature. and one which reflects the strength of generative models for imitation. One corollary of our key contributions is summarized the follow- ing informal statement. The main technical insights leading to the proof of the theorem detailed in the bullet points below it, and depicted in Figure 1.
expert demonstrations

---

Theorem (informal), Consider generative behavior cloner î that learns to predict sequences of expert actions on horizon H, along with low-level controllers that locally stabilize the trajectories. Then, with suitable data noising strategy, for all times h S H,
Flexpert & imitator trajectories disagree at some time / by 2 E]
S Oiss (HE+ x² Σn Eexpert,h h (Wi (P expert actions: P Pimitator actions)]
where Eexpert, A (M (P expert actions imitator actions)] denotes 1-Wasserstein distance in ap- propriate metric between the conditional distribution over expert and imitator actions given the observation at time step h, and where Oiss hides constants depending polynomially on the stability properties of the low-level controllers, defined formally in Section 3.1.
We now detail the key ingredients of our results.
1. We imitate stochastic demonstrators that may exhibit both complex correlations between actions in their trajectories (e.g. be non-Markovian) and multi-modal behavior. The natural object to imitate in this setting is the conditional probability distribution of expert actions given recent states, but marginalized over past states. We require said conditional action distribution to be learnable by generative model, but otherwise arbitrarily complex: in particular, the conditional distribution of an expert actions given the state can discontinuous (in any natural distance metric) as function of state, as in the bifurcation depicted in Figure (rigght).
2. We obtain rigorous, theoretical guarantees and without requiring either interactive data col- lection (c.g. DAGGER [57. 40]), or access to gradients of the expert policy (as in [ASIL[50]). Instead, we replace these assumption with an oracle, described below, which synthesizes sta- bilizing, low-level policies along training demonstrations the green arrows in Figure ((eeft) This mirrors recent work on generative behavior cloning that find that providing state-commande through inverse dynamics controllers [33, 2] or position-commant controllers of end effectors [19] leads to substantially improved performance.
3. We also apply a subtle-yet-significan modification to popular data noising strategy, which we show yields both theoretical and empirical beneifts. Data noising ensures a helpful property we denote total variation continuity that interpolates between modes in probability space (without naively averaging their trajectories in world space). This effectively "fills in the missing gaps" in bifurcations, as indicated by yellow arrows in Figure 1.
Our main results, Theorems 1 and 2, are reductions from imitation of complex expert trajectories to supervised generative learning of specific conditional distribution. For concreteness, Theorem instantiates the generative modeling with Denoising Diffusion Probabilistic Models (DDPMs) of sufficient regularity and expressivity (as investigated empirically in [19, 48, 26]). and establishes end-to-end guarantees for imitation of complex trajectories with sample complexity polynomial in relevant problem parameters. Our analysis framework exposes that any sufficient powerful genera- tive learner obtains similar guarantees. Finally, we empirically validate the benefits our proposed smoothing strategy in simulated robotic manipulation tasks. We now summarize the algorithmic choices and analytic ideas that facilitate our reduction.
Abridged Related Work. Due to space, we defer full comparison to past work Appendix B. DDPMs, proposed in [29, 60], along with their relatives have seen success in image generation [62, 55], along with imitation learning (without data augmentation) [33, 19, 48], which is the starting point of our work. Smoothing data augmentation ubiquitous in modern imitation learning [40] and approach corresponds that of [36] but with noise added at inference time. Despite the benefits of adaptive data collection [58, 40], adaptive demonstrations are more expensive to collect. Previous analyses of imitation learning without adaptive data collection have focused classical control- theoretic notions of stability, notably incremental stability, [68, 27, 50], which require continuity, Markovianity, and often determinism, and preclude the bifurcations permitted in our setting.
2 Setting
Notation and Preliminaries. Appendix A gives full review of notation. Bold lower-case (resp. upper-case) denote vectors (resp. matrices). We abbreviate the concatenation of sequences via 21.x = (Z,....,2,, z. Norms || are Fuclidean for vectors and operator norms for matrices unless
3

---

otherwise noted. Rigorous probability -theoretic preliminaries are provided in Appendix F. In short, all random variables take values in Polish spaces X' (which include real vector spaces), the space of Borel distributions on X' is denoted A(X)) We rely heavily on couplings from optimal transport theory: given measures X
and X' ~ P' on X' and X" respectively, (PP,'') denotes the space of joint distributions E A(X x X") called "couplings"" such that (X, XX" l has marginals X ~ P and X' P. A y) denotes the space of conditional probability distributions Q y + A(X), formally called probability kernels Appendix F rigorously justifies that, in our setting, all conditional distributions can be expressed as kernels (which we do throughout the paper without comment). Finally Ixc (E) denotes the indicator taking value 1 if & is true and otherwise.
Dynamics and Demonstrations. We consider a discrete-timee control system with states X, X := Rd and inputs u, E U := RT,,, obeying the following nonlinear dynamics
x (xx, Ut), 1 1.
(2.1)
Given length T N, call sequences Pr = (x1:T-1, u1:T) Pr:= XT Ut trajectories. For simplicity, we assume that (2.1) is deterministic and address stochastic dynamics in Appendix N. 'Though the dynamics are Markov and deterministic, we consider stochastic and possibly non- Markovian demonstrator, which allows for the multi-modality described in the Section 1.
Definition 2.1 (Expert Distribution). Let Dexp. E (r) denote an expert distribution over trajec- tories be imitated. Dx, denotes the distribution of X1 under Pr (X1T++,, UI:T)
Dexp-
Primitive Controllers. Our approach is to imitate not just actions, but simple local control poli- cies. In the body of this paper, we consider affine mappings X' + l (redundantly) parameterized as x + + K(x x): we call these primitive controllers, denoted with x = (u, x, K) E K. We describe the synthesis of these controllers in Appendix D and extend our results to general families of parameterized controllers in Appendix E. We argue in Appendix E that primitive controllers are in fact standard practice, and implicit via robotic position control in many applications of diffusion to robotic behavior cloning.
Chunking Policies and Indices. The expert distribution Deep may involve non- Man-Markovian se- quences of actions. We imititate these sequences via chunking policies. Fix a chunk length Tchunk E N and observation length Tobs S. Tchunk. and define time indices t, = (h - 1)Tchmuk + 1. For simplicity, we assume Tchunk divides T, and set H /CThaunk. Given a Pr E Pr, define the trajectory-chunks and observation chunks
Sh [Xta-15ta 16,--1t, -1) ES 3
(trajectory-chunks)
Tebank
O = (Xt, Tobs + +1dd Un -obb 1:41 -:1 -1) O
P Toba -1
(observation-chunkk)
for h > 1, and 5 = o x, (for simplicity. we embed o, into Pro-- via zero- aro--pading). We call
Tehunt-length sequences of primitive controllers composite actions
aa Kit,
A
KC Tehunk
(composite actions)
A chunking policy  = (m)) consists of functions Ta mapping observation-chunks on, to distribu- tions A(A) over composite actions and interacting with the dynamics (2.1) by a KK (o)), and executing u, = )x.). We let d = Teluuk (dg + d. + dzd,) denote the dimension of the space A of composite actions. The chunking scheme is represented in Figure 2, demonstrating the rationale for using primitive controllers over open-loop actions. Remark C.1 describes our
rationale for studying states over generic observations, and considering time-dependent policies.
Desideratum. The quality of imitation of a deterministic policy is naturally measured in terms of step-wise closeness of state and action [68, 50]. With stochastic policies, however, two rollouts of even the same policy can visit different states. We propose measuring distributional closeness via couplings introduced in the preliminaries above. We define the following losses, focusing on the marginal distributions between trajectories.
Definition 2.2. Given E > and a (chunking) policy ग,, the (marginal distribution) imitation loss is
Leargge (Tr) : max inl, Py, [max { [|xx x || u } e]. where the infinum over all couplings fa between the distribution of Pr under Doxp and that induced by the policy æ as described above, such that P xx =x]] 1.

---

%
Reel
Apel
Expert Trajectory
Action chunking
Controller chunking
Figure 2: Graphical comparison of an action-chunk based policy (left) described in [19], versus the primitive-controller chunking policy (right) proposed this paper. The primitive controller paradigm allows for stabilizing back to the original expert trajectory, whereas using generated actions in an open-loop fashion may cause divergence from the expert in the presence of unstable system dynamics. We refer to composite actions as the sequence of primitve controllers given on the right.
Under stronger conditions (whose necessity we establish), we can also imitate joint distributions over actions (Appendix J). Observe that Lin.e S. Emarg.e> and that both losses are equivalent to Wasserstein-tyDe tttee metrics on bounded domains. These losses are also equivalent to Lévy-Prokhorov metrics [64] under re- re-scaling of the Euclidean metric (even for unbounded domains), and also corre- spond to total variation analogues of shifted Renyi divergences [5, 6]. While empirically evaluating these infima over couplings is challenging, Lmarg.e upper bounds the difference in expectation be- tween any bounded and Lipschitz control cost decomposing across time steps, states and inputs, and Lün,r upper bounds differences in final-state costs; see Appendix J for discussion.
Diffusion Models. Our analysis provides imitiation guarantees when chunking policies TT select an via a sufficiently accurate generative model. Given their recent success, instantiate our analysis for the popular Denoising Diffusion Probabilistic Models (DDPM) framework [18, 41] that allows the learner to sample from a density q E A (IR)) assuming that the score V log q is known to the learner. More precisely, suppose the learner given an observation оμ and wishes to sample a ~ q(-(o;,) for some family of probability kernels q(-l-). A DDPM starts with some at. sampled from a standard Gaussian noise and iteratively "denoises" for each DDPM-time step S
a// a
( j) +2-N((0,0 a(0.a²1)
(2.2)
S. (an, On aj), formally defined for any continuous argument t I Ja to be s, on, t) == V. log Z., [4] on). where Te
where so.A (2 J) estimates the true
(-Ion) (o,)) is the distribution
(0) is sampled from the target distribution we which to sample of eaaa/ (0) + v1 - v1-e-22 Biyy with a
from, and 7 (N, I) is standard Gaussian. We denote by DDPM(s0, ox) the law of a sampled according to the DDPM using so on. as a score estimator. Preliminaries on DPPMs are detailed in Appendix L.
3 Conditional sampling with stabilization suffices for behavior cloning
We show that trajectories of the form given in Definition 2.1 can be efficiently imitated if (a) we are given a synthesis oracle, described below, that produces low-level control policies that locally stabilize chunks of the trajectory with primitive controllers and (b) we can learn to generate certain appropriate distributions over composite actions, i.e. sequences of primitive controllers. All the following results apply to affine primitive controllers introduced in Section and assume that the system dynamics are second-order smooth and locally stabilizable. In Appendix E, we show that our results still hold with general families of parametric primitive controllers, provided that these controllers induce the same local stability guarantee.
The synthesis oracle. We say primitive controller (ef. Section 2) K1.T E K"T is consistent with trajectory = (XI:++1, uIr)) E Pr if X,
and ū, = for all t E [T]: note that this implies that (x,)) u, for all t. synthesis oracle synth maps Pr + K such that, for all Pr E Pr, f1.T = synth(P7) is consistent with Pr- For our theory, we assume access to a synthesis oracle at training time, and assume the ability to estimate conditional distributions over joint sequences of primitive controllers; Appendix K explains how this can be implemented by solving Ricatti equations if dynamics are known (e.g. simulator), smooth, and stabilizable. In experimental environment, control inputs are desired robot configurations, which the simulated
5

---

robot executes by applying feedback gains, As discussed in Appendix E, learned or hand-coded low-level controllers are popular in practical implementations of generative behavior cloning. We discuss the merits of studying imitation learning with synthesis oracle in depth in Appendix C.3.
Notions of distance. While restricting ourselves to affine primitive controllers, our approximation eπrоr of generative behavior cloner is measured in terms of optimal transport distances that use the following "maximum distance." Given two composite actions a (0117chamk X
X1sTebunik 19Tccaunk))
and a' (1Thhmkk 1eThuntt 1 K Kistehene ), we define
dmax (a, ==
max IgkSTaduukk
il
uللll + | - X + K KAIl
(3.1)
Distances between policies are defined via natural optimal transport costs. Given two policies π (mT), n/ = (T(() and observation chunk on, we define an induced optimal transport cost
(o)) T (ox)) == inf P (,),))))> [dmax (a): a/h)) > c],
where the inf, denotes the infinum over all couplings between as T (0x) and ai, TT/ (ox). A corresponds to a relaxed Lévy-Prokhorov metric [64], and can always be bounded, via Markov's inequality, by A (TT,, 7 0n)) di (T (On), Ty (on)), where W1 (ox), n (o))) denotes the 1- Wasseersteiin distance between an TA (on) and a/, ~ (o,).
3.1 Incremental Stability and the Synthesis Oracle.
We assume that synthesis oracle above produces incrementally stabilizing control gains, in the sense first proposed by [9]. Incremental stability has emerged as a natural desirable property for imitation limitation [50, 68, 27], because it forces the expert to be robust to small perturbations of their policy. We now supply a formal definition. Given primitive controller k : Rdd - R define the closed loop dynamic map fet.x (x, bu) == f(x, x(x) + du). Thus, composite action a is consistent with a trajectory chunk $ (Xi:ramm +1 u1 if x,-1 = faxx: (x, 0) for 1 S S Fehunk-
Definition 3.1 (Time-Varying Incremental Stability). Let y(-) be a class K function, B(:--) be class KL function, and let a = (6g No..,,......... k2) denote a sequence of primitive controllers (i.e. a composite action when т = Tchunk). Given a sequence of input perturbations Sun,7 E (Rd=)" and initial condition & Rd, let say that composite action a is time-varying incrementally input-to-state stable (t-Iss) with moduli ((s. if for all E. E' E R2 0 S i S F, /| ||x((0 .r. {) x² (Su1) <'Ill S B - E'Il, r) + (maxigagi-1 /u, l). Given parameters Cy, Cg > O we say that a is local-t-Iss at Eo if the above holds only for all E SSurr such that ||E Soll. IIE - Eoll I ce and max; [|Su,] S Cy.
< fel.a; (x( E), Su;), with x = &. We
Incremental stability implies that as the inital conditions - + O and maxos ||8u,| - O. the trajectories induced by taking rolling out from E. and rolling out a from 5 with additive in- put perturbations du1,r tend to zero in norm. This behavior needs only hold for initial conditions in a small neighborhood of a nominal state En- Importantly, the perturbations Su are fixed per- tubrations of inputs, applied to the closed loop behavior under the controllers. Our notion of in- cremental stability are similar too, but sublty different similar notions of past work. We provide an extended comparisons in Appendix F.2. Our main assumption is that the synthesis oracle described above produced primitive controllers which are consistent with, and incrementally stabilizing for, the demonstrated trajectories. Figure demonstrates the effect of stabilizing primitive controllers.
Assumption 3.1. We assume that our synthesis oracle enjoys the following property. Let Pr = (X1-++1 )I:T) ~ Dexp- and let K1.7 = synth (r)), partitioned into composite actions a1:Hr with (x) (x x,) + ú, We assume that, with probability one, N1r is consistent with pr? and that, for each 1 S h < H, an. = =K + +Tammn-1) )) is local t-Iss at X1,, with moduli y, ß and parameters cp. c5 > We further assume that y and take the form
y(u) = &y . u, B(u,k) = ōße (k-1)4p -ge-(111)4p u, Ty, Cp 00, LB E (0,
Bellow, we recall definitions of classes of comparison functions in nonlinear control [38] as follows: we say a univariate function 22 - 1220 class K if it is strictly increasing and satisties y(0) 0. We
say a bivariate function B R220 x Σgo > R2o class KL if x + B(a, t) class K for each t 2 0. and
t + B(z,, t) is nonincreasing in t.
Note that this implies X; and ūr Ur.

---

(b)
Montly Left
Equal Split
Monily liggh
Right Mode
Figure 3: Graphical representation of total variation continuity (TVC) using the running "left mode/right mode" example. Panel (a) depicts a policy a which is TVC. and thus interpolates between left and right modes probabilistically. Importantly, the TVC property applies to the distribution over composite actions, i.c. sequences of primitive controllers, as, Definition 3.3; this ensures, example, that following the left mode from slightly to the right of the obstacle (purple dotted line) still stabilizes to the idcalized left mode trajectory (red). In panel (b), we consider policy which for TVC applies to the sequences of raw control inputs (which is not what occurs in Definition 3.3). This can lead to naive mode-switching that collides with the gray obstacle.
Lastly, we assume that for the expert trajectories and the primitive controllers drawn as above, holds that satisfy max[[|x]]] || Rayn and | < Rx with probability one.
In Appendix K, we show that Assumption 3.1 holds whenever (a) the dynamics of our system are smooth (but not necessarily linear!) (b) the affine gains are chosen to stabilize the Jacobian lin- earizations of the system around the nominal trajectory.
Definition 3.2 (Problem constants). Throughout, we refer to constants C1 O22 C3, C1. Cs > 0, which are polynomial in the terms in Assumption 3.1, and which are defined formally in Appendix K.
3.2 Simplified guarantees under total variation continuity
This section presents our main theoretical result: if one learns a chunking policy á that can compute the conditional distribution of composite actions time steps given observation-chunks, then stochastically smoothed version of this policy, 7.. has low imitation error. Define, for any length r E N, the trajectory distance between trajectories p (X1+++1, U1:)) k.r, p' = (x1+++1 n/ E 9
diraj(P. p') = max
| xx11 V max ||u u'/ ISkST+1
(3.2)
ISAST
In particular, we define deraj (O), of,)) and dsrnj(s,, s%,) by viewing these trajectories of length Tobs -1 and Tehunks respectively. Lastly, we define a per-timestep restriction of the expert dis- tribution. In this section, we consider the case where the learner policy satisfies total variation continuity (TVC) condition, defined below.
Definition 3.3 (TVC of Chunking Policies). We say that chunking policy (mT) is total vari- ation continuous with modulus "/rve R>00 -> Rgo. written TVVC. if, for all E [H] and any observation-chunk. on, 0%, 3 Tohu-1 -1 (V(TA(O)), (o,))) S (drrj (O,, o),)).
We depict the TVC property using our running left obstacle example in Figure 3. We stress that, in Definition 3.3, the TV bound TV( (o,), Ta (o applies the composite actions consisting of primitive controllers 2n = Kz, Tchunk- ~ TA (o,): does not upper bound the TV distance between raw control inputs. Indeed, ensuring TVC of the latter can lead to the failure modes depicted in Figure 3(b). Next, we extract an expert "policy" from the expert demonstrations.
Definition 3.4 (Expert "policy" with synthesized controllers). For h e [H), we let Dexp,h denote the joint distribution of (as, on), induced by drawing trajectory Pr (xI:7+1, uI.T) ~ Dexp from the expert distribution, K1.T = synth(pr) (pr)
associated primitive controllers, let- ting о₁ = (Xt, -Tute + Ut, -oa +1, be the associated observation-chunk at time h, and an = 011 the associated composite action. We let x.)+) O - A(A) denote the condition distribution of аи oy under D Dexp.h.
The conditional distributions m.)()) are estimated when training generative model to predict a from observations o₁. Note that 7 (-) (and Dexp,it is defined in terms of both expert demonstration
7

---

from Des Deep and the associated synthesized primitive controllers. In Lemma J.6, we show that when the synthesis oracle K1.TT = synth (r) produces primitive controllers consistent with the trajecto- ries, than x=' = (xt)) produces the same marginals over states as Dexpi that is, ( = O.
Theorem 1. Suppose Assumption 3.1 holds, and suppose that 0 < < c2. and Tchunk 2 C3- Then, for any non-decreasing non-negative Tive(+) and "Vv chunking policy म, it holds that Lmarg.e(ft I (Trve(E) + Eh=1 Eon.DDrp. ((e/o)) (on), (nn))) which is at most 1l (e) + aL > Bon.DDep.. [Widd (T)())), (on)))
The above result reduces the marginal imitation error of á to the sum over optimal transport errors between and a O₁ chosen by the expert demonstrators. Thus, these are small, the local stabilization properties of the primitive controllers guaranteed by Assumption 3.1 ensure that errors compound at most linearly in problem horizon. The key ideas of the proof are given Appendix D, via a general template for imitation learning of general stochastic policies. This template is instantiated with a details in Appendix J.
3.3 A general guarantee via data noising.
To circumvent assuming that the leamer's policy is TVC, we study estimating the conditionals un- der a popular data augmentation technique [36], where the learner is trained to imitate the condi- tional sequence of бλ where бn (o,,,, o²I) adds -a-variance Gaussian noise to the true observation-chunk, To understand this better, consider the following smoothed policy:
Definition 3.5 (The smoothed policy), Let â = (ft) be a chunking policy. We define the smoothed policy to ()) by letting (- (λ) be distributed as #x (- 6,., where on. ~ No I'I).
Appendix J.7.2 show's that Pinsker's 's inequality implies noising automatically enforces TVC This suggests that we can use some form of data noising enforce the TVC property in Definition 3.3. Let's now consider a related problem: trying to estimate the optimal distribution over composite actions conditioned on a noised observation. This gives rise deconvolution of the expert policy, which can be thought as an inverse operation of data noising.
Definition 3.6 (Noised Data Distribution and Deconvolution Policy). Let Dexp, be as in Defini- tion 3.4. Define Desp.a. as the distribution over (ōn: an.) generated by (on, an) Dexp,h and б₁ ~ _Noo,, We define the decomollution policy ", as the conditional distribution of a on under Dexp.o.h-
Analogously to x², the policy ad h. is what generative model trained to generate a, from noised observations o; of o₁, ~ DDxpp learns to generate. Our next theorem states that, if our ग approximates the idealized conditional distributation of composite actions given noised observations, then a.. the smoothed policy, imitates the expert distribution with provable bounds on its imitation error:
Theorem 2 (Reduction to conditional sampling under nosing). Suppose Assumption 3.1 holds. Let C1y.... C5 0, defined in Definition 3.2, and let 11ss denote term which is upper and lower bounded by a x times a polynomial in those constants and their inverses. Then, for < 11s (1), ), if we choose a = E e/ ( dzz + log(1/e)) and let Tchunk S C3 and Tehunk
Tabs 2 Lp log(cr/e),
Cmarg.e (Rx) < 1ss (EH Vobe - (Vdg + log( + Einn Bon (ice) (Tiec.O.A A (ōn), An (ōx)
which
is
upper
bounded by at most 1 (EH /Tboa (Vd, + log(1/E)) +
EK Eo Davporch 22
1
Wi.dmax
( TT (ōn), tn (n)(
To reiterate, Theorem guarantees imitation of the distribution of marginals and final states of D Dexp by replacing the explicit TVC assumption with noising, and the resulting guarantee applies to the smoothed policy Ao which adds smoothing noise back in. Appendix J gives a number of additional results. In Appendix I, we show that the proof framework, outlined in Appendix D, which under lies the proofs of Theorems and 2, is essentially sharp the worst case. Moreover, Appendix C.3, we discuss the merits and drawbacks of our use of the synthesis oracle, and how it circumvents some of the challenges encountered in behavior cloning in past work. The key intuition behind the proof of Theorem 2 is depicted in Figure 4, and full proof sketch is deferred to Appendix C.2
8

---

Figure 4: Multi- modal demonstrations traverse an ob- stacle left or right, exhibiting a pure bifurcation. We consider perturbing expert data the right mode (blue circle) noised datum (gray circle). We show that generative behavior cloners learn to deconvolve this noise, creating a virtual "replica" sample (red circle) following the left mode, such that the replica and orig- inal are i.i.d. given the noised onc. When the red cir- cle's primitive controllers are rolled from from the blue circle, this Ieads to a trajectory (yellow circle) which interpolates across the bifurcations. Marginalizing over this process, the yellow trajectories probabilistically in- terpolate between red and blue modes, and (approxi- mately) match the per-tim per-time-sted simp marginal over expert distributions.
Left Mode
Right Mode
Replica Trajectory
Noised State
4 HINT: Instantiating Data Noising with DDPMs
We now instantiate Theorem by showing that one can learn a policy for which the error terms in Theorems 1 and 2 are small by fitting a DDPM to noise-smoothed data. Our proposed algo-
Algorithm Hierarchical Imitation via Noising at Inference Time (HINT) [h]
I: Initialize Synthesis oracle synth, sample sizes N Nexp: Naug E N, a 2 0, DDPM size > 0,
DDPM horizon J, function class {So) JeE, gain magnitude I > empty data buffer < 0.
X. For smoothing, set 0 and Naug
2: for n = 1, 2, Nexp do
3: Sample Pr (I1.T+1, u1:T) Dexp and set K1.T synth(p)
% Segment 01.H from Pr and â1.и from Rir
4: for i 1,2, 2, ..... ,,...,,,uur Naug and h 1,,,.... H do Nion,, I²)), in Unif([J] and Yn NO (Ina)=1).
5: Sample
6:
+ D appped (1(a), on, Jb: Yn. h)])
7: Fit 0 E arg mingee LDDPM (f, D) and let न (#x) be given by #(- o^) DDPM(S0, on)-
8: return A. (n.,)). by smoothing as per Definition 3.5.
rithm, HINT (Algorithm 1) combines DDPM-learnngg of chunked policies as [19] with a popular form of data-augmentt auttenugmentttionn [36]. We collect Nesp expert trajectories, synthesize gains, and segment trajectories into observation-chunks о₁ and composite actions a as described in Section 2. We perturb each оμ to form Naug chunks o;, as well as horizon indices j E [J] and inference noises to our data D. We end the training
(0, (I).)"I). and add these tuples (an, ōh.jh, Tho f2) phase by minimizing the standard DDPM loss [62]:
LoDPM (0, ) = Eia,, Ena.. Yh Su.k (e- (e-ajan + -I- e--aj nno on in )x)
(4.1)
Our algorithm differs subtly from past work in Line 8: motivated by Theorem noise back in at test time. Here, the notation DDPM(s0.N. oN((), I²I) means, given о%2 perturb it to Õд ~ (on,,, r²I), and sample a ~ DDPM Ōμ). We now state an informal guarantee for HINT, deferring formal statement to Appendix C.5.
add smoothing
Theorem (Informal Theorem). Suppose that the system dynamics are smooth and that Assump- tion 3.1 holds for the linearized system. Then there choice of the parameters in HINT that polynomial in all problem parameters such that for Naxp- polynomially large in problem parameters, Lmarg, (Ra) < θ (Tot Tohe ddr log(1/e))) with high probability.
4.1 Experimental Results
In this section, we demonstrate the benefits of diffusing low level controllers, and of our approach to data noising. We explain the environments in greater detail, along with all training and compu-

---

10
0.3
Natrslled Reward
0.5
Nomolied 0.6
0.4
No Grits, No:
Golos, Xei
No Guins, ae0
Csin. em00
0.2
No Colts N
Golos Na1
No Goins, en
Calas em003
N-5
N-5
No Colts, x.D1
c.B.
Nimbored Trgesteiiz
Figure 5: Performance of diffusing chunks of actions -6--1 -1 ("No Gains") versus jointly dif- fusing actions -4 reference states X6m-1:4-11 and gains - for a 2-D quadrotor system with thrust-and-toreee coandd-trque--assse control. Different noise levels and number of trajectories N are shown. Mean and standard deviation are shown across 5 training seeds.
Push-T
Can Pick and Place
Square Avanmbly
on
0.6
Normalteed
8
12
088
Sigms
Sigga
Signa
Blanelie HINT
Blaeeino
Tlaeelioo
Baselino HINT
Figure 6: Performance of baseline and noise-injected á o W. HINT policy for different o. We use training seeds with 50 and 22 test trajectories per seed for PushT and Can and Square Environments respectively. Mean and standard deviation of the test performance on the 3 best checkpoints across the 4 seeds are plotted. The values correspond to noise in the normalized [-1, 1] range.
tational details in Appendix O, Figure 5 compares the performance of diffusing (chunks of) raw control inputs to diffusing (chunks of) gain matrices for a canonical model of a 2-d quadrotor. We find that diffusing gain matrices yields dramatic improvements in performance, in particular allow- ing a single imitated trajectory to outperform learning raw control inputs from 10 demonstrations.
Next, empirically evaluate the effect on policy performance of our proposal to inject noise back into the dynamics at inference time. We consider three challenging robotic manipulation tasks studied in prior work: Push'T block-pushing [19]; Robomimic Can fick-and-Place and Square Nut Assem- bly [42] (we direct the reader to Chi et al. [19] for an extensive empirical investigation into the performance of diffusion policies in the un-noised
0 regime). We display the results of our experiments in Figure 6. Observe that the performance degredation of the replica policy from the unnoised = 0 variant is minimal across all environments and even leads to slight but noticeable improvement in the small-noise regime for PushT (and low-data Can Pick and Place). In the pres- ence of non-neglig noise HINT significantly outperforms the conventional policy (obtained by noising observations at training but not test time), as predicted by our theory.
5 Discussion
This work considerably loosened assumptions placed the expert distribution by introducing synthesis oracle responsible for stabilization. How best to achieve low-level stabilization remains an open question. We hope that this work encourages further empirical research into improving the stability of imitation learning, either via the hierarchical route proposed in this paper or via new innovations.
com/ pfr ommerd/ 'Code for PUshT, Robomimic experiments can be found at com/pfrommerd. /tteerdd////aaae stanza/ crctuusion_pooccee pt.. Quadrotor experiments are in https://githe cow
10

---

Acknowledgments
We would like to thank Cheng Chi for his extensive help in running the code in [19] and Benjamin Burchfiel for numerous insightful discussions and intuitions about DDPM policies. Lastly, we thank Alexandre Amice for his helpful feedback on an earlier draft of this manuscript. AB acknowl- edges support from the National Science Foundation Graduate Research Fellowship under Grant No. 1122374 as well as the support of DOE through award DE-SC0022199. MS and RT acknowl- edge support from Amazon.com Services LLC grant; PO# 2D-06310236. DP and AJ acknowledge support from the Office of Naval Research under ONR grant N00014-23-1-2299.
References
[1] S. Abu-El-Haija, N. Kothari, J. Lee, P. Natsev, G. Toderici, B. Varadarajan, and S. Vijaya- narasimhan. Youtube-8ni 8m: large-scale video classification benchmark. arXiv preprint arXiv:160.008677 2016.
[2] A. Ajay, Y. Du, A. Gupta, J. Tenenbaum, T. Jaakkola, and P. Agrawal. Is conditional generative modeling all you need for decision-making? arXiv preprint arXiv:2211.15657 2022.
[3] A. Ajay, A. Gupta, D. Ghosh, S. Levine, and P. Agrawal. Distributionally adaptive meta reinforcement learning. arXiv preprint arXiv:2210.00 10.033100 2022.
[4] A. Ajay, S. Han, Y. Du, S. Li, A. Gupta, T. Jaakkola, J. Tenenbaum, L. Kaelbling, A. Srivastava, and P. Agrawal. Compositional foundation models for hierarchical planning. arXiv preprint
arXiv:23009.mm 08587. 2023.
[5] Altschuler and K. Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35:3788- 3800, 2022.
[6] M. Altschuler and S. Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. arXiv preprint arXiv:2302.10249 2023.
[7] B. D. Anderson and J. B. Moore. Optimal control: linear quadratic methods. Courier Corpo- ration, 2007.
[8] O. Angel and Y. Spinka. Pairwise optimal coupling of multiple random variables. arXiv preprint arXiv: 1903v:1903.00000 00600, 2019.
[9] D. Angeli. A Yyapunov approach incremental stability properties. IEEE Transactions on Automatic Control, 10-421, 2002.
[10] M. Bansal, A. Krizhevsky. and A. Ogale. Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst. arXiv preprint
2018.
[11] L. Bartlett and Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
[12] P. I.. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint. Acta numerica, 30:87-201, 2021.
[13] A. Block, Y. Mrouch, and A. Rakhlin. Generative modeling with denoising auto-encoders and langevin sampling. arXiv preprint arXiv:2002.00110 2020.
[14] A. Block, Y. Mroueh, A. Rakhlin, and J. Ross. Fast mixing of multi-scale langevin dynamics under the manifold hypothesis. arXiv preprint arXiv: 166, 2020.
[15] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp. P. Goyal, L. D. Jackel, M. Monfort, U. Muller, Zhang, al. End to end learning for self-driving cars. arXiv preprint arXiv: 1604.07316, 2016.
[16] J. D. Chang, M. Uehara, D. Sreenivas, R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data without great coverage. arXiv preprint arX1v:2106.03207, 2021.
[17] I. Chen, K. Lu, A. Rajeswaran, K. Lee, A. Grover, M. Laskin, P. Abbeel, A. Srinivas, and Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 15014744-50097 2021.

---

[18] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In NeurlPS 2022 Workshop on Score-Based Methods, 2022.
[19] C. Chi, S. Feng. Y. Du, Z. Xu, E. Cousineau. B. Burchfiel, and S. Song. Diffusion policy: Visuomotor policy learning via action diffusion. arXiv preprint arXiv:2303. 043337, 2023.
[20] S. Dasari, F. Ebert. S. Tian, S. Nair, B. Bucher, K. Schmeckpeper, S. Singh, S. Levine, and
C. Finn. Robonet: Large-scale multi-robot learning. arXiv preprint arXiv:1910. 1215, 2019.
[21] P. De Haan, D. Jayaraman, and S. Levine. Causal confusion in imitation learning. Advances in Neural Information Processing Systems, 32, 2019.
[22] R. Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
[23] C. Finn, T. Yu, T. Zhang. P. Abbeel, and S. Levine. One-shot visual imitation learning via meta-learning. In Conference on robot learning, pages 357-368. PMLR, 2017.
[24] D. Foster and A. Rakhlin. L-infinity vector contraction for rademacher complexity. arXiv preprint arXiv: 991.0646,, 6, 2019.
[25] J. W. Hagood and B. S. Thomson. Recovering a function from a dini derivative. The American Mathematical Monthly, 113(1):34 46, 2006.
[26] P. Hansen- I. Kostrikov, M. Janner, J. G. Kuba, and S. Levine. Idql: Implicit q-learning as an actor-critic method with diffusion policies. arXiv preprint arXiv:2304. 10573, 2023.
[27] A. Havens and B. Hu. On imitation learning of linear control policies: Enforcing stability and robustness constraints via Imi conditions. In 202/ American Control Conference (ACC), pages 882- 382-887.10 IEEE, 2021.
[28) D. Hendrycks, S. Basart, N. Mu, S. Kadavath, F. Wang, E. Dorundo, R. Desai, T. Zhu, S. Para- juli, M. Guo, et al. Jacob steinhardt et justin gilmer. the many faces of robustness: critical analysis of oft-of-distribution generalization. arXiv preprint arXiv:2006. /6241, 2020.
[29] J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-688 2020.
[30] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 50(2):1-35, 2017.
[31] A. Hussein, E. Elyan, M. M. Gaber, and C. Jayne. Deep imitation learning for 3d navigation tasks. Neural computing and applications, 29:389-404, 2018.
[32] A. Hyvärinen and Dayan. Estimation of non-normalized statistical models by score match-
ing. Journal of Machine Learning Research, 6(4), 2005.
[33] M. Janner, Y. Du, J. B. Tenenbaum, and S. Levine. Planning with diffusion for flexible behavior synthesis. arXiv preprint arXiv:2205.0999
2022.
[34] C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:1902.037/55 2019.
[35] I. P. Kaelbling and T. Lozano-Pérez. Hierarchical task and motion planning in the now. In 2011 IEEE International Conference on Robotics and Automation, pages 1470-1477 IEEE, 2011.
[36] I.. Ke, J. Wang, Bhattacharjee, B. Boots, and Srinivasa. Grasping with chopsticks: Com- bating covariate shift in model-free imitation learning for fine manipulation. In 202/ IEEE International Conference on Robotics and Automation (ICRA), pages 6185-6191. IEEE, 2021.
[37] M. Kelly, C. Sidrane, K. Criggs-Camphell, and M. J. Kochenderfer. Hg-dagger: Interactive imitation learning with human experts. In 2019 International Conference on Robotics and Automation (ICRA), pages 8077-8083, IEEE, 2019.
[38] H. Khalil. Nonlinear Systems. Pearson Education. Prentice Hall, 2002. ISBN 9780130673899.
URL https: //oopss//books.... http:/boooooooggel..ee/o cwm/books iidit_dddgAAAAA....
[39] I. Kostrikoy, D. Yarats, and R. Fergus. Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. arXiv preprint arXiv:2004. 13649, 2020.
[40] M. Laskey, J. Lee, R. Fox, A. Dragan, and K. Goldberg. Dart: Noise injection for robust imitation learning. In Conference on robot learning. pages 143-156. PMLR, 2017.
12

---

[41] H. Lee, J. Lu, and Y. Tan. Convergence of score-based generative modeling for general data distributions. In International Conference on Algorithmic Learning Theory, pages 946-985. PMLR, 2023.
[42] A. Mandlekar, D. Xu, J. Wong, S. Nasiriany. C. Wang, R. Kulkarni, L. Fei-Fei, S. Savarese, Y. Zhu, and R. Martin-Martin. What matters in learning from offline human demonstrations for robot manipulation. arXiv preprint arXiv:2108. 03298, 2021.
[43] T. Marcucci, Umenberger, P. A. Parrilo, and R. Tedrake. Shortest paths in graphs of convex sets. arXiv preprint arXiv:2 11565, 2021.
[44] A. Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
[45] M. Mezard and A. Montanari. Information, physics, and computation. Oxford University Press, 2009.
[46] D. Misra. Mish: A self regularized non-monotonic activation function. arXiv preprint
1908 18681, 2019.
[47] A. Q. Nichol and P. Dhariwal. Improved denoising diffusion probabilistic models. In Interna- tional Conference on Machine Learning, pages 8162-8171. PMLR, 2021.
[48]
Pearce, T. Rashid, A. Kanervisto, Bignell, M. Sun, R. Georgescu, S. Macua, S. Z. Tan, I. Momennejad, K. Hofmann, et al. Imitating human behaviour with diffusion models. arXiv preprint arXiv:2301. 10677, 2023.
[49] E. Perez, F. Strub, H. De Vries, V. Dumoulin, and A. Courville. Film: Visual reasoning with a general conditioning layer. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
[50] D. Pfrommer, T. Zhang. S. Tu, and N. Matni. Tasil: Taylor series imitation learning, Advances Neural Information Processing Systems, 15:20122-20177 2022.
[51] D. Pfrommer, M. Simchowitz, T. Westenbroek, N. Matni, and S. Tu. The power of learned locally linear models for nonlinear policy optimization. arXiv preprint arXiv:2305.096. 2023.
[52] Y. Polyanskiy and Y. Wu. Information Theory: From Coding to Learning. Cambridge Univer- sity Press, 2022+.
[53] M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674- 1703. PMLR, 2017.
[54] A. Rakhlin, K. Sridharan, and A. B. Tsybakov. Empirical entropy. minimax regret and minimax risk. Bernoulli Society for Mathematical Statistics and Probabiliiy,, 2017.
[55] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.0612. 2022.
[56] O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Asiited Intervention-MICCAl 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings. Part III 18, pages 234-241. Springer, 2015.
[57] S. Ross and D. Bagnell. Efficient reductions for imitation learning. In Proceedings of the thir- teenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[58] S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured predic- tion to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Pro- ceedings, 2011.
[59] N. M. Shafiullah, Z. Cui, A. A. Altanzaya, and L. Pinto. Behavior transformers: Cloning k modes with one stone. Advances in neural information processing systems, 35:22955-22966 2022.
13

---

[60] J. Sohl-Dickstein, E. Weiss. N. Mabeswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2266 PMLR, 2015.
[61] J. Song, C. Meng, and S. Ermon. Denoising diffusion implicit models. arXiv:2010.02502, 2020.
arXiv preprint
[62] Y. Song and S. Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[63] Y. Song, S. Garg, Shi, and S. Ermon, Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pages 574-584, PMLR, 2020.
[64] V. Strassen. The existence of probability measures with given marginals. The Annals of Math- ematical Stafistics, 36(2):423-439 1965.
[65] X. Sun, S. Yang, and R. Mangharam. Mega-dagger: Imitation learning with multiple imperfect experts. arXiv preprint AXXIv:2303300634 2023.
[66] R. Tedrake. Lqr-trees: Feedback motion planning on sparse randomized trees. 2009.
[67] R. Thoppilan, D. De Freitas, Hall, N. Shazeer, A. Kulshreshtha, H.-T. Cheng, A. Jin, T. Bos,
L. Baker, Y. Du, et al. Lamda: Language models for dialog applications. arXiv preprint
arXiv:2201.08239 2022.
[68] S. Tu, A. Robey, T. Zhang, and N. Matni. On the sample complexity of stability constrained imitation learning. In Leamning Dynamics and Control Conference, pages 180-191. PMLR, 2022.
[69] R. Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
[70] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, E. Kaiser, and I. Polo- sukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[71] R. Vershynin. High-dimensional probability: An introduction with applications in data sci- ence, volume 47. Cambridge university press, 2018.
[72] C. Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
[73] C. Villani et al. Optimal transport: old and new, volume 338. Springer. 2009.
[74] P. Vincent. A connection between matching and denoising autoencoders. Neural com- putation, 23(7):1661-1674 2011.
[75] M. J. Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
[76] T. Westenbroek, M. Simchowitz, M. Jordan, and S. S. Sastry. On the stability of nonlinear receding horizon control: geometric perspective. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 742-749. IEEE, 2021.
[77] Y. Wu and K. He. Group normalization. In Proceedings of the European conference on com- puter vision (ECCV), pages 3-19, 2018.
[78] T. Zhang, Z. McCarthy, O. Jow, D. Lee, X. Chen, K. Goldberg, and P. Abbeel. Deep imita- tion learning for complex manipulation tasks from virtual reality teleoperation. In 2018 IEEE International Conference Robotics and Automation (ICRA), pages 5628-5635. IEEE, 2018.
[79] S. Zhao and A. Grover. Decision stacks: Flexible reinforcement learning via modular genera- tive models. arXiv preprint arXiv:2306. 06253, 2023.
[80] T. Z. Zhao, V. Kumar, S. Levine, and C. Finn. Learning fine-grained bimanual manipulation with low-cost hardware. arXiv preprint arXiv:2304. 1..304.3770,, 13705, 2023.
14


Reviews:
[{"review_id": "mlEuwxOXck", "reviewer": "Reviewer_NhZ6", "summary": "This work proposes a theoretical framework for learning sequential decision-making with diffusion models. The authors show that with the conditions of (1) a suitable low-level \"stability\" guarantee and (2) a stochastic \"continuity\" property of the learned policy, the imitator can provably accurately estimate the \"non-Markovian\" policy of the demonstrators. The low-level \"stability\" is assumed in oracle primitive controllers, which are then composed by diffusion models that are learned with DDPM loss. Since the desired stochastic continuity is not guaranteed for an arbitrary demonstrator policy, the authors then propose a data augmentation technique that adds noise to the trajectories, making the resulting policies continuous. Their experiments validate that the proposed data augmentation alleviates imitator policy's degradation in noisy environments. ", "questions": "Apart from the question in Weakness, I hope the authors would like to answer the following: \n\nL172, what is K? It does not seem to be defined. \n\nI am not sure if this question is appropriate, but how can we know Assumptions 3.1, 3.2, and 3.3 are true in reality? ", "limitations": "As stated by the authors in L239-243, the major limitation of this work is that the desired \"stability\" is given since the proposed algorithm relies on either synthesized primitive controllers (in our analysis) or low-level stabilizing controllers built into problem environments (in our experiments). Relaxing such restriction can be a future research direction. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: I am not very familiar with the current literature of learning theory. But proving the learnability of a hierarchical imitator appears to be novel to me. \n\nQuality: The analysis presented in this paper is of high quality. I liked the formal narrative where each mathematical object is clearly defined before used. The authors also provide detailed derivation in their appendix. \n\nClarity: Even though this paper adopts heavy notation and formulas, the authors did a good job in explaining each mathematical object carefully. Through out my read, there are lines where I need to pause and think, but barely one makes me confused. The flow is very smooth. \n\nSignificance: I am not an expert in the literature of learning theory, so my evaluation of the significance may be biased. The proposed algorithm itself does not seem to be super significant. But conceptually connecting adding noises to \"total variation continuity\" is interesting to me. ", "weaknesses": "My major concern is that even though the presented analysis is interesting and self-contained, it doesn't seem to provide too much insight into developing a new algorithm or improving existing ones. The proposed algorithm is a consequence of the analysis, but it is not obvious why we need it. I hope the authors would like to discuss more about the potential influence of the presented analysis and algorithm in their feedback. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback.  Our approach suggests a natural algorithmic paradigm for imitation learning: \n\nRather than imitating raw actions, one should imitate simple *control policies*. This paper addresses the simple case of linear gains, but in principle, one could imitate goals for goal-conditioned RL-trained reaching policies (we are working on this as an empirical follow-up). In the revision, we will better emphasize that this paper suggests a hierarchical algorithm design; we have been working on experience with synthesized gains for a 2D quadrotor to demonstrate this in the revised version. \nWe show that adding smoothing noise at inference time if one adds noise at train time benefits performance.  While this intervention may seem small, it is important to note that our experiments show reasonable improvement over the baseline of adding the augmentation only at train time.\n\nIn addition to potential algorithmic suggestions, our analysis explains the remarkable efficacy of diffusion policies imitating complex behavior in recent work [1,2,3]. As we stress in the introduction, no previous analysis can account for successful imitation of possibly multi-modal trajectories and our work is the first to do so.\n \n# Regarding The  Assumptions\nAsm 3.1 holds for many nonlinear systems - we are currently working with a collaborator to implement our hierarchical approach on a hydroelastic simulator of a robot with soft-end effectors, which satisfies this smoothness assumption (and experimentally has good sim-to-real transfer). \n\nAs we remark after Asm 3.2, this holds whenever we synthesize gains from solving a Ricatti equation (and can be checked by inspecting the Ricatti value function). \nAsm 3.3 is a standard learning-theoretic assumption for “is learnable”, but as we show in a revision, a sufficient condition is simply that the DDPM has good validation loss (i.e. generalization under the expert distribution), which we show holds in practice.\n\n# Typos\n\n 1. The term $K_{k-1}$ in L172 should be $\\bar K_{k}$. \n\n2. On L169, we state that $$\\bar{x}_k, \\bar{u}_k,\\bar{K}_k$$ \nare feedback terms min a given sequence of primitive controllers.  We will correct this typo in the revision.\n\n#References\n\n[1] C. Chi, S. Feng, Y. Du, Z. Xu, E. Cousineau, B. Burchﬁel, and S. Song. Diffusion policy:Visuomotor policy learning via action diffusion. arXiv preprint arXiv:2303.04137, 2023.\n\n[2] Hansen-Estruch, I. Kostrikov, M. Janner, J. G. Kuba, and S. Levine. Idql: Implicit q-learning as an actor-critic method with diffusion policies. arXiv preprint arXiv:2304.10573, 2023\n\n[3] Pearce, T. Rashid, A. Kanervisto, D. Bignell, M. Sun, R. Georgescu, S. V. Macua, S. Z. Tan, I. Momennejad, K. Hofmann, et al. Imitating human behaviour with diffusion models. arXiv preprint arXiv:2301.10677, 2023\n"}, {"review_id": "YT1K0EUIl4", "reviewer": "Reviewer_RM4v", "summary": "This is a theoretical paper that studies imitation learning from demonstrations that exhibit multi-modality. This method separate the demonstrations into chunks, then uses diffusion models to learn a policy conditioned on the memory of hindsight prefix of the trajectory to output an affine time-varying controller. Gaussian noises are added to the demonstrations for data augmentation, and in the learned controllers' outputs to enhance performance. ", "questions": "1. In line 5 of Algorithm 1, shouldn't the mean of \\gamma_h be 0 instead of a_h? In Eq.3.1, \\gamma_h is sampled from D to compose the a DDPM loss function of which the update rule matches Eq 2.2. Then, \\gamma_h corresponds to the \\gamma in line 155, which is a standard Gaussian.  \n2. If \\gamma_h indeed has its mean equal to a_h, how to understand the sum in Eq3.1? Why adding such noised action to e^{-\\alpha j} a_h? \n3. If \\gamma_h has its mean equal to 0, why matching s_\\theta,h(...) with \\gamma_h, a Gaussian noise? \n4. What do ...\\vee... \\leq max ... mean in line 275? Applying \\vee to real values?", "limitations": "The author mentioned the limitation of the proposed approach in the paper. The limitation, however, does not undermine the quality and contribution of this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: this paper is original in proposing an algorithm to learn hierarchical policy by leveraging diffusion models and injected noises from potentially non-markovian expert demonstrations.\nQuality: this paper has strong theoretical support. \nClarity: the algorithms and theories are clearly explained.\nSignificance: the paper provides a new insight to solving non-markovian imitation learning problems by combining trajectory optimization tools, distribution learning in a hierarhical manner.", "weaknesses": "In the experiment, three benchmarks are utilized. However, it is not mentioned in the maintext nor in the appendix how non-markovian and multi-modal the demonstrations are. As a result, the validity of the proposed algorithm is less convincible despite all the theoretical guarantees. \nAlso, the symbols in this paper are too complicated to parse. There seem to be some symbols misusage in some of the formulas, making those formulas confusing. Please refer to the question section for the those potential errors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and helpful feedback. One of our benchmarks, Push-T was proposed by [1] as an explicitly multi-modal task; Figure 4 in [1] illustrates that one can go left or right around the T-object. We will be sure to include a reference to this figure in our revision. \n\nThough the primary prupose of our paper is theoretical in nature, we are currently working on a 2D quadrotor environment as well. In our preliminary findings, the replica policy consistently outperforms the deconvolution policy. This suggests that adding noise at inference time does indeed improve performance. We suspect to see the benefits of adding noise once we also finish our implementation of diffusing feedback gains, and with a Wasserstein measure of discrepancy to capture the fact, shown in our analysis, that the replica policy matches the expert distribution on marginals at each time step but not, necessarily, on the joint trajectory distribution. We will include all these additional experiments in the final version. \n\nWe apologize for the notational overhead. We replaced the $\\circlearrowleft$ symbol with $\\mathrm{rep}$ for replica-quantities in the revision. We made sure to use consistent subscript-types and letter names for all quantities - W is a kernel, P a distribution, subscript-$\\mathrm{dec}$ is for deconvolution, $\\pi$ is a policy, and so on. We provide a table of notation in Appendix A for review, and plan to expand it in the revision.   We will now address the further questions:\n\n1 & 2. Thank you for catching this typo. $\\gamma_h$ is indeed suppose to be mean zero and we will correct it in the revision.\n3. When $\\gamma_h$ is mean zero Gaussian, we recover the standard de-noising score matching loss where we add gaussian noise to a point and try to predict the noise. While this may seem unintuitive, many works, see for example [2] cited in our paper, show that this is equivalent to learning the score.\n4. The distances $d_\\mathcal{S}$ and $\\mathsf{d}_{\\mathrm{TVC}}$ are distances and thus real numbers, so the ordering is the standard one on the real line - x \\vee y = max\\{x,y\\}. We will include this in the “notation” section.\n\n[1] C. Chi, S. Feng, Y. Du, Z. Xu, E. Cousineau, B. Burchﬁel, and S. Song. Diffusion policy:Visuomotor policy learning via action diffusion. arXiv preprint arXiv:2303.04137, 2023.\n\n[2]S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. Zhang. Sampling is as easy as learning the score: theory for\ndiffusion models with minimal data assumptions. In NeurIPS 2022 Workshop on Score-Based Methods, 2022.\n"}, {"review_id": "Fyp4Xk3POn", "reviewer": "Reviewer_VsMF", "summary": "The paper introduces an imitation learning framework for handling multimodal and non-Markovian demonstrations. This is done by using a hierarchy where rather than predicting low-level controls directly, the learner predicts sequences of primitive controllers. These controllers are time-varying affine mappings from states to control inputs. The authors show that this approach allows us to reformulate our task as imitation in a composite MDP, where composite states and actions refer to subsequences of trajectories and primitive controllers respectively. To handle multimodality, they use diffusion models (DDPM) to parameterize the learner. The primary contribution of the paper is to bound the loss of the proposed approach (TODA), relying primarily on the stability of the lower-level controllers. Some empirical results are demonstrated on some robot manipulation tasks, where the proposed algorithm outperforms the baseline policy.", "questions": "What is $d_{\\mathcal{A}}$? Not the formal definition, but conceptually what is it?\n\nWhat is the purpose of the replica policy? I'm not sure I understand how this part of the proof functions.\n\nIs the smoothing kernel $W_{\\sigma}$ the same as the data augmentation function?\n\nI don't understand L304-307.\n\nTypos:\n\nL52, \"... which is both both ...\"\n\nL60, \"Wassertstein-like\"\n\nL106, \"... we assume that (2.1) deterministic ...\"\n\nL342, \"subtley\"\n\n===\nI have read the rebuttal and bumped my score up slightly.", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The high-level motivation for the approach is sound and the practical algorithm seems to perform well.\n\nThe paper is comprehensive and filled with technical content and derivations. I went through the analysis in the main body of the paper and did not find any glaring errors, although certain parts were hard to parse (see below).", "weaknesses": "Honestly I have a hard time following Section 4. More detailed questions are below. Given that the crux of the contribution lies in this theoretical analysis, I'm more than happy to adjust my score post-rebuttal if I can get some things cleared up.\n\nTraining a diffusion model to use low-level controllers as primitives as not new [1].\n\nWould have preferred a more comprehensive experimental evaluation with competitive baselines, but given the theoretical contribution I suppose this isn't fully necessary.\n\nThe proposed approach heavily relies on sufficiently smooth dynamics and the existence of an oracle which can synthesize primitive controllers given trajectories. This is fairly restrictive and prevents this work from being applicable to many existing control/robotics applications. Given that the contribution is primarily theoretical, this isn't a major issue for me.\n\n[1] Ajay, Anurag, et al. \"Is conditional generative modeling all you need for decision-making?.\" arXiv preprint arXiv:2211.15657 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Novelty and Theoretical Contributions\n\nThanks for your feedback. We agree that training a diffusion model with low-level primitives is not a new idea [1], and (as noted in our paper) in most works that use diffusion, they apply position control rather than torque control which can also be viewed as primitive. The purpose of this paper is to give a rigorous analysis of this approach, and to re-formulate what *stability* means in this hierarchical context (which is not found in the theoretical literature). We provide a rigorous framework and analysis to that end. We provide a complementary way to obtain primitives - namely through linear gains from Riccati equations. By contrast, [1] requires an inverse dynamics model (which may be challenging non one-step controllable systems). \n\n# Future Experiments\n\nWhile the focus of this paper is mainly theoretical, in the revision, we will also include a quadrotor experiment with synthesized gains to showcase our method. We are also working with collaborators to apply the method (with synthesized gains) to a hydroelastic simulator of a soft whole-body robot manipulator. Notice that in this simulator, as in *any differentiable simulator*, *we can synthesize gains*, so that the method is practically feasible. While addressing non-smooth systems is an interesting algorithmic direction for future work, the  assumptions {smoothness, Jacobian stabilizability} can be replaced by incremental stability of the primitive controllers (which these assumptions yield for linear primitive controllers as a special case). We will expand on this point in the revision. \n\n\n# Action Distance:\n\nRecalling that a composite action is just a sequence of $\\tau_c$ primitive controllers with parameters in Euclidean space, \nintuitively $d_A$ is the maximal Euclidean distance between the parameters of the primitive controller on each of the time steps.  In order to provide greater generality to locally stable systems, we add a term that is infinite for when two sequences of primitive controllers are too far apart for us to be able to say anything about them.  Intuitively, one can ignore the indicator function if you condition each step of the proof (and the results) on the event that actions and induced trajectory are sufficiently close together for local stability to hold.\n\n# Replica Policy\n\nThe *replica policy* is a fictitious policy that we use in our analysis. It represents what would happen if one \n\n(a) perfectly trained a generative model to predict  $a_h \\mid s_h + w_h$ (actions given smoothed states), and \n\n(b) selected actions at state x and step h by applying $\\mathrm{trained}~\\mathrm{model}(s_h + w_h)$. \n\nBy contrast, the *deconvolution policy* is trained as in (a) but does not use smoothing noise as in (b). The name ``replica’’ comes from the fact that we can view the process of smoothing and then deconvolving a state as creating a *replica* of that state, which is close to it, and has the same marginal distribution (this is how it’s used in physics).   The key insights are that (1) training a policy with data augmentation and then inference-time noise injection converges to the replica policy and (2) unlike the deconvolution policy, the *replica policy*, is \"close’’ to the $\\pi^\\star$ policy in many ways which are important for the analysis. We did our best to explain this in the text. \n\nFor example, if $s_h ~ P^\\star_h$, the marginal distribution over actions under the replica policy and the $\\pi^\\star$ are the same. This means that, following the replica policy, we essentially see similar states that we did to follow pi^*. Thus, we don’t suffer the problem of finding states that are out of the distribution of the demonstrator. By avoiding this distribution shift, our analysis shows that our learned policy imitates the replica policy. Because the replica policy is close to $\\pi^\\star$, argue that imitating the replica policy (in joint distribution) suffices to imitate $\\pi^\\star$ in terms of state marginals.   The true policy $\\pi_h^\\star$ maps state $x$ -> distribution over action $a$, and the *deconvolution policy* maps $x$ -> the distribution of $\\pi_h^\\star(x) | x_h+w_h = x$, under $x_h ~ P^\\star_h$, then the *replica policy* maps $x \\mapsto x+w$ to a deconvolution policy evaluated at $x+w$. One way to think of this is saying that $x$ is smoothed to a point $x’$, and deconvolved to another point $x’’$. \n\nThe crucial property is that, if $x\\sim P^\\star_h$, then \n $(x,x’’ \\mid x)$ are i.i.d random variables.\nYes the smoothing kernel is the same as the data augmentation; our proof holds in greater generality than simple gaussian noise and so we use a different symbol to emphasize this generality. In the revision, we apply consistent notation to avoid this confusion\nSee the explanation on the replica policy.\n\n# Typos\nThank you for finding the typos; these will be corrected in the revision.\n\n\n[1] Ajay, Anurag, et al. \"Is conditional generative modeling all you need for decision-making?.\" arXiv preprint arXiv:2211.15657 (2022)."}, {"review_id": "BsbCCGiaap", "reviewer": "Reviewer_rprV", "summary": "This paper proposes a theoretical framework for studying the imitation of expert demonstrations in nonlinear dynamical systems. The framework guarantees accurate imitation of expert trajectories by invoking low-level controllers and a stochastic continuity property of the learned policy. The authors also introduce an algorithmic trick for ensuring total variation continuity, which combines a popular data-augmentation regimen with augmentation noise at execution time. The paper includes a detailed proof of the framework and empirical validation of the proposed augmentation strategy in simulated robotic manipulation tasks", "questions": "1. I think it is still important to comprehensive study of this method. What’s the influence of hyperparameters to this method? Should there be any ablation study included in this paper?\n2. What’s the computational complexity of the proposed algorithmic trick for ensuring total variation continuity?", "limitations": "1. The paper assumes that the low-level controllers are either learned or implicit in position-command control, which may not always be the case in practice.\n2. The paper does not provide a detailed analysis of the effect of hyperparameters on the performance of the proposed framework.\n3. The paper does not consider the effect of imperfect state estimation or perception on the accuracy of the imitation policy.\n4. The paper does not address the issue of exploration in the imitation learning setting, which is an important problem in reinforcement learning.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes a novel theoretical framework for studying the imitation of expert demonstrations in nonlinear dynamical systems.\n2. The framework guarantees accurate imitation of expert trajectories by invoking low-level controllers and a stochastic continuity property of the learned policy.\n3. The authors introduce a novel algorithmic trick for ensuring total variation continuity, which combines a popular data-augmentation regimen with augmentation noise at execution time.\n4. The paper includes a detailed proof of the framework and establishes stability guarantees for sequences of primitive controllers in non-linear control systems.\n5. The proposed augmentation strategy is empirically validated in simulated robotic manipulation tasks.\n6. The paper provides a comprehensive review of related work in the field of imitation learning and compares the proposed framework to past work in the appendix.", "weaknesses": "1. The paper relies on either synthesized primitive controllers or low-level stabilizing controllers built into problem environments to take advantage of local stability. Developing a more comprehensive approach to stability (perhaps one that does not require explicit gain synthesis and extends to non-smooth systems) is an exciting direction for future work.\n2. The paper focuses on simulated robotic manipulation tasks, and it is unclear how well the proposed framework would generalize to other domains or real-world scenarios.\n3. The paper does not provide a detailed analysis of the computational complexity of the proposed algorithmic trick for ensuring total variation continuity.\n4. The paper does not compare the proposed framework to state-of-the-art methods in the field of imitation learning on benchmark datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for the feedback.  We will address each point below.\n\n# Weaknesses\n\n1.The main technical contribution of the paper is formalizing a notion of hierarchical stability that is flexible enough to accommodate multi-modality. Note that our analysis extends to any synthesis oracle that provides increment lly stable primitive controllers, significantly generalizing linear gains. This generalization will be included in the revision. Such more general synthesis oracles can be implemented from reinforcement learning interactions with a simulator of the environment.\n\n2.While the simulation-to-real problem is well-known and well-documented, it is standard to first understand an algorithm’s benefits in simulation before moving to hardware.  While our paper focused mainly on theoretical advances, we included some simulation experiments for the sake of concreteness, as well as to demonstrate the practicality of our algorithm.\n\n3. The data augmentation is simply adding Gaussian noise to observations, so its computational complexity is negligible compared to model training.  We will emphasize this in the revision. Notice that we never explicitly constructed the replica policy in our analysis, it is merely a tool to describe the idealized behavior of a policy noise at test and inference time in the limit of large sample sizes.\n\n4. Our work is primarily about providing novel theoretical insights into the use of generative-modeling based policies for imitation learning. We provide the first rigorous mathematical guarantees for imitating behaviors, far surpassing the generality of past work. While we make numerous algorithmic suggestions, including noising-at-inference and synthesizing low level controllers, the goal of the work is first and foremost mathematical.\n\n# Questions\n\n1. Because the primary algorithmic modification is to add noise at inference time, as opposed to only adding the augmentation at train time, this was the benchmark to which we compared our algorithm empirically.  There are many empirical studies of diffusion models applied to similar tasks.  We also conducted a dataset ablation by subsampling the number of expert trajectories trained.  \n\n2. The addition of gaussian noise at inference time ensures total variation continuity (TVC). Thus, we do not need to alter the weights of the networks to ensure TVC (and thus the computational overhead is negligible). Indeed, we prove in the appendix that for any function $f(x)$, the random function $x \\mapsto f(x + \\sigma w)$, where $w \\sim \\mathcal{N}(0,I_d)$ is $O(\\sigma)$-total variation continuous, *regardless of the function* $f$ \n\n\n# Limitations\n\n1. We agree access to low-level controllers is a limitation. As noted in the introduction, pure supervised learning is not sufficient for provable guarantees on imitation learning. Past works have required interactions with the environment (DAGGER [1], DART [2]), or imitating a much simpler, stabilizing behaviors  with gradient/adversarial queries (TaSIL [3]). We present the first result without adaptive data collection for general behaviors. We show that we replace the stabilizing expert from TaSIL [3] with an oracle that synthesizes stabilizing primitive controllers, which stabilize only locally, which is much weaker. While this does not include all practical situations, we can synthesize these gains whenever the dynamics are smooth and we have a good differentiable simulator. We are working with collaborators who use hydroelastic simulation for whole-body manipulation to test out our method. \n\n2. See (1) in Question; moreover, as is common in theoretical works, we do not focus on hyperparameter optimization. We do, however, show the importance of the smoothing parameter sigma in our experiments. \n\n3. As we remark, because visuomotor experiments have been done in similar settings in many other works (cited in the paper), we consider direct state access for our experiments for convenience.  Note that our theory does allow for much greater generality.\n\n4. While exploration is certainly important in reinforcement learning, this paper is concerned with the topic of purely offline imitation learning, a paradigm that has seen increased recent interest due to the fact that it does not require the often unrealistic assumption of online interaction that defines online RL.\n\n[1] Ross, Stéphane, Geoffrey Gordon, and Drew Bagnell. \"A reduction of imitation learning and structured prediction to no-regret online learning.\" Proceedings of the fourteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 2011.\n\n[2] Laskey, Michael, et al. \"Dart: Noise injection for robust imitation learning.\" Conference on robot learning. PMLR, 2017.\n\n[3] Pfrommer, Daniel, et al. \"Tasil: Taylor series imitation learning.\" Advances in Neural Information Processing Systems 35 (2022): 20162-20174.\n"}, {"review_id": "c04bHTDOPb", "reviewer": "Reviewer_dAio", "summary": "The paper presents a simple hierarchical approach for non-Markovian imitation learning along with a rigorous theoretical analysis.\nThe method trains a high level policy, given by a Denoising Diffusion Probabilistic Model (DDPM), to predict a sequence of linear control gains based on a state-action history.\nThe DDPM is trained in supervised fashion (using the standard DDPM loss) where the labels (the controller gains) are computed from the given expert trajectories using an oracle (e.g. based on linearizations along the trajectory). To address covariate shift (compounding errors) in imitation learning the method applies a form of data augmentation by adding noise to the state-action history. In contrast to prior work, these perturbations are also applied during inference, which is theoretically motivated and empirically shown to improve imitation performance.\nThe main contributions seems to be the thorough analysis of this method, which leads to Theorem 1, a bound on the imitation performance. \nThe applicability of the proposed method is demonstrated on simulated robot tasks, although no comparisons with prior work are provided.", "questions": "Line 216 states that \"each term in (3.2) can be made arbitrarily small by decreasing the amount of noise $\\sigma$ in the augmentation [...]\". Isn't the first term anti-proportional to the noise?\n\nLine 274: \"all sequences $s'\\_1 = s\\_1$ and  $s'\\_{h+1} = s\\_{h+1}$ [...]\". I'm wondering if this should be \"all sequences $s'\\_h = s\\_h$ and  $s'\\_{h+1} = s\\_{h+1}$ [...]\"!?\n\nLine 325: \"We let the expert policy $\\pi^*$ be the concatenation of policies $\\pi\\_h^*$ [...]\". Is this an additional assumption? Clearly, the expert will in general not apply this particular form of a hierarchical policy.", "limitations": "I think that the limitations are sufficiently clear.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Novelty & Relevance\n-------------------\nBoth the method and in particular the analysis seem to be novel and non-Markovian imitation learning is an important field of research. I would not expect the proposed method to outperform other (theoretically less well understood) methods, but I do think that the general approach of using a diffusion model as a high-level policy to predict controller gains could be used by future work that is more focused on practical performance. Furthermore, the theoretical analysis could be valuable for theorists in the field of imitation learning. However, I am not very familiar with related theoretical work and cannot assess well, which aspects/techniques of the analysis might be most relevant.\n\nSoundness\n---------\nThe algorithm seems sounds. I guess one could argue that it might be simpler and more stable if the higher-level policy would predict a trajectory segment instead of the gains, given that we assume access to an oracle that can provide us with stabilizing gains. However, querying the oracle could be too costly, so directly predicting the gains can be sensible.\n\nI cannot fully confirm the accuracy of the theoretical results because verifying the complete derivations would take significant effort. However, the claims (including Theorem 1) seem reasonable, apart from non-critical issues (see Questions below).\n\nClarity\n-------\nThe paper is well-written. The paper is very strict in terms of notation, definitions, and statements, which increases clarity by reducing ambiguities.", "weaknesses": "Clarity\n-------\nAlthough I mentioned the rigor as a strength, it also feels a bit pedantic. Furthermore, it is cumbersome to keep track of the different constants and definitions making the paper hard to read and making it easy to get lost in details.\n\nEvaluation\n----------\nDespite the fact that the contributions are mainly in the theoretical analysis, quantitative comparisons with alternate methods that have been used in these environments would be useful. I don't know which prior work was used in that environment that also provided code, but I assume it should be possible to find suitable baselines that can be easily tested.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback.  \n# Clarity\nRegarding the issue of clarity, we will clean up the notation and provide greater intuition for the mathematical abstractions in the revision.  For example, we have now replaced $\\circlearrowleft$ symbol with $\\mathrm{rep}$ for replica-quantities.\n\n# Empirical Evaluation\nOn the subject of empirical evaluation, note that our paper’s primary contribution is in the novel mathematical contributions that allow us to prove the first general imitation learning guarantees in regimes where the demonstrator policies are arbitrarily unstable.  The empirical section is intended to demonstrate that our proposed intervention (adding noise at inference time) is beneficial with respect to the benchmark of standard practice, which is adding noise only at training time but not at inference time. For the revision, we will also include experiments on 2D quadrotor – a system known to be unstable – to demonstrate the benefits of synthesizing gains.\n\nThere has been a lot of excellent empirical work that has demonstrated the advantages of diffusion-based policies over prior approaches. We refer the reader to [1] for further exposition.\n\n# Questions\nWe will now address the questions:\n1. Thank you for pointing this out, we will make this more clear in the revision.  What we mean to say is that as the number of demonstrators grow, we may take epsilon arbitrarily small and thus, by tuning the noise sigma appropriately, our proposed algorithm can achieve arbitrarily small loss with sufficiently many demonstrations.\n2. To clarify, we mean all sequences $(s_{1:H+1}',a_{1:H}')$ whose initial condition is $s_1' = s_1$, and whose dynamics obey $s_{h+1}' = F_h(s_h',a_h')$. \n3. The crucial part of the stability is that it is *multi-step*, so that the differences between actions $a’_h$ and $a_h$ can accumulate over time. Due to space constraints, we opted for the compact definition but can add more clarification in the revision. \n4. This is not an extra assumption, but rather a definition.  Note that while we colloquially refer to policies, formally we consider a distribution on trajectories.  We then rigorously *define* a policy at each time step $h$ to be the conditional distribution of an action given the history up to time $h$.  Thus a global policy (defined on all time steps) is just the concatenation of each of the policies at each time step.  This is equivalent to factoring a joint distribution as a product of conditional distributions.  We will better clarify this in the revision.\n\n[1] C. Chi, S. Feng, Y. Du, Z. Xu, E. Cousineau, B. Burchﬁel, and S. Song. Diffusion policy:Visuomotor policy learning via action diffusion. arXiv preprint arXiv:2303.04137, 2023.\n"}]

Author rebuttal:

Meta-review: The submitted paper was reviewed by 5 reviewers, 4 of whom recommended accpetance and 1 of whom recommended rejection. Discussions between reviewers and authors took place addressing most of the reviewers' questions. The reviewers appreciate the originality and rigour of the submitted paper but have concerns regarding the experimental evaluation, some of the made assumptions in the theoretical analysis, and the presentation ("complicated to parse", misconceptions/unclarities about the high-level implications and implications for future work). Based on my own reading of the paper, I also got the impression, that the paper could be significantly stronger and more impactful, if the authors simplify the presentation in the main paper and focus stronger on the high-level presentation, implications, and take-aways (for future work). Stil, I think the paper has sufficient merit to be accepted and hence I am recommending acceptance. Nevertheless, I encourage the authors to carefully revise their paper in line with the reviewers comments and issues highlighted in the dicussions, making the most out of the available 9 pages.
Decision: Accept (poster)