Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning
Authors: Dylan J Foster
Adam Block
Dipendra Misra
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Imitation learning
statistical learning theory
reinforcement learning theory
Primary area: learning_theory
TL;DR: Through a new analysis of behavior cloning with the logarithmic loss, we show that it is possible to achieve horizon-independent sample complexity in offline imitation learning, closing an apparent gap between online and offline IL.

Abstract: Imitation learning (IL) aims to mimic the behavior of an expert in a sequential decision making task by learning from demonstrations, and has been widely applied to robotics, autonomous driving, and autoregressive text generation. The simplest approach to IL, behavior cloning (BC) is thought to incur sample complexity with unfavorable quadratic dependence on the problem horizon, motivating a variety of different online algorithms that attain improved linear horizon dependence under stronger assumptions on the data and the learner’s access to the expert. 

We revisit the apparent gap between offline and online IL from a learning-theoretic perspective, with a focus on general policy classes up to and including deep neural networks. Through a new analysis of BC with the logarithmic loss, we show that it is possible to achieve horizon-independent sample complexity in offline IL whenever (i) the range of the cumulative payoffs is controlled, and (ii) an appropriate notion of supervised learning complexity for the policy class is controlled. Specializing our results to deterministic, stationary policies, we show that the gap between offline and online IL is not fundamental: (i) it is possible to achieve linear dependence on horizon in offline IL under dense rewards (matching what was previously only known to be achievable in online IL); and (ii) without further assumptions on the policy class, online IL cannot improve over offline IL with the logarithmic loss, even in benign MDPs. We complement our theoretical results with experiments on standard RL tasks and autoregressive language generation to validate the practical relevance of our findings.

Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning
Dylan J. Foster
Adam Block
Microsoft Research dy wtwpsssseeesessssoooosooooooo
Department of Mathematics
MIT ablock@mi edu
Dipendra Misra
Microsoft Research
di dipendrakuman mi watssrddttabricssccmm
Abstract
Imitation learning (IL) aims to mimic the behavior of an expert in a sequential decision making task by learning from demonstrations, and has been widely applied to robotics, autonomous driving, and autoregressive text generation. The simplest approach IL., behavior cloning (BC), thought to incur sample complexity with unfavorable quadratic dependence on the problem horizon, motivating a variety of different online algorithms that attain improved linear horizon dependence under stronger assumptions on the data and the learner's access to the expert.
We revisit the apparent gap between offline and online II. from a learning- learning-theoretic theoretic perspective, with focus on the caalizablewelllsspecffee setting with general policy classes up to and including deep neural networks. Through a new analysis of behavior cloning with the logarithmic loss, show that is possible achieve pprizon-indepenin
sample complexity in offline IL whenever (i) the range of the cumulative payoffss controlled, and (ii) an appropriate notion of supervised learning complexity for the policy class is controlled. Specializing our results to deterministic, stationary policies, we show that the gap between offline and online II. is smaller than previously thought: (i) it is possible to achieve linear dependence on horizon in offline II. under dense rewards (matching what was previously only known to be achievable in online IL); and (ii) without further assumptions the policy class, online IL cannot improve over offline IL with the logarithmic loss, even in benign MDPs. We complement our theoretical results with experiments on standard RL tasks and autoregressive language generation to validate the practical relevance of our findings.
Introduction
Imitation learning (IL. is the problem of emulating expert policy for sequential decision making by learning from demonstrations. Compared to reinforcement learning (RL), the learner in IL does not observe reward-based feedback, and must imitate the expert's behavior based on demonstrations alone: their objective is to achieve performance close to that of the expert on an unobserved reward function. Imitation learning motivated by the observation that in many domains, demonstrating the desired behavior for a task (e.g., robotic grasping) is simple, while designing a reward function to elicit the desired behavior can be challenging. IL is also often preferable to RL because removes the need for exploration, leading to empirically reduced sample complexity and often much more stable training. Indeed, the relative ease of applying IL (over RL methods) has led to extensive adoption, ranging from classical applications in autonomous driving [63] and helicopter flight [1] to contemporary works that
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

MuJoCo
Atari
0.20
horizon
0.30
50
0.15
horizon 100
horizon 100
horizon 200
0.25
horaznn 200
Expected Regret
horizon 300
Expected Regret
horizon
horizon 400
0.20
horizon 500
0.05
0.15
0.00
0.10
-0.05
0.05
-0.10
200
400
50
100
150
200
Number Trajectories
Number of Trajectories
(a)
(b)
Figure I: Suboptimality of policy learned with log-loss behavior cloning (LogLossBC) as function of the number of expert trajectories, for varying values of horizon H. In each environment, an imitator is trained according to LogLossBC and the regret with respect to the expert is reported, with reward normalized to be prrizon-independent (a) Continuous control with MuJoCo environment Walker2d- v4. (b) Discrete control with Atari environment BeamFidderNoFrameskip v4. For both environments, we find that the regret is independent of horizon (or in the case of Atari, slightly improving with horizon), as predicted by our theoretical results. Full experimental details are provided in Appendix C.
leverage deep learning to achieve state-of-the-art performance for self-driving vehicles [15, 6, 44], visuomotor control [30, 103), navigation [45], and game Al [46, 90]. Imitation learning also offers conceptual framework through which to study autoregressive language modeling [21, 13], and number of useful empirical insights have arisen as a result of this perspective. However, a central challenge limiting broader real-world deployment is to understand and improve the reliability and stability properties of algorithms that support seneral-purpose (deep/neural) function approximation.
In more detail, imitation learning algorithms can be loosely grouped into offline and online approaches. Offline imitation learning algorithms only require access to a dataset of logged trajectories from the expert, making them broadly applicable. The most widely used approach, behavior cloning, reduces imitation learning to a standard supervised learning problem in which the learner attempts to predict the expert's actions from observations given the collected trajectories. The simplicity of this approach allows the learner to leverage the considerable machinery developed for supervised learning and readily incorporate complex function approximation with deep models [10, 70]. On the other hand, BC seemingly ignores the problem of distribution shift, wherein small deviations from the expert policy early in rollout lead the learner off-distribution to regions where they are less able to accurately imitate. This apparent error amplification phenomenon has been widely observed empirically [70, 54, 13], and motivates online or interactive approaches to imitation learning [70, 72, 71, 78], which avoid error amplification by interactively querying the expert and learning to correct mistakes on-policy.
In theory, online imitation learning enables sample complexity guarantees with improved (linear, as opposed to quadratic) dependence horizon for favorable MDPs. Yet, while online imitation learning has found empirical success [73, 52, 38, 6, 26, 51, 7, 108, 59]. online access to the expert can be costly infeasible in many applications, and offline imitation learning remains dominant empirical paradigm. Motivated by this disconnect between theory and practice, we aim to understand to what extent the apparent gap between offline and online imitation learning fundamental. We ask:
Is online imitation learning truly more sample-efficient than offline imitation learning, or can existing algorithms or analyses be improved?
1.1 Background: Offline and Online Imitation Learning
To motivate our results, we begin by formally introducing the offline and online imitation learning frameworks, highlighting gaps in current sample complexity guarantees concerning horizon dependence. We take a learning-theoren perspective, with a focus on general policy classes.
Markov decision processes. We study imitation learning in episodic Markov decision processes. Formally, a Markov decision process M A,,, H) consists of a (potentially large) state
2

---

space X. action space A, horizon H, probability transition function P {Pr [Prlizor where Ph : X' A + (()), and reward function r = {ra)m= where X x A - R. A (randomized) policy is sequence of per-timestep functions π {m X + { k=1- The policy induces a distribution over trajectories (I1, (1,,),,,......... ( aH, rn) via the following process. The initial state is drawn via #1 (2)) then for h ,..... H: op =((r)) Th (3r. ax). and ÆĄ-1 ~ (z as). For notational convenience, we use IH+1 to denote a deterministic terminal state with zero reward. We let [+] and [-] denote expectation and probability law for (x1, a1)................... HH aH) under this process, respectively.
The expected reward for policy is given by ((r E given by (z) = E" [E TM 24 z] and Q7 (z, a) = E Ew== The 2h = a, a].
D h= rn]. and the value functions for ı
H
Reward normalization. To study the role of horizon in imitation learning in a way that disentangles the effects of reward scaling from other factors, we assume that rewards are normalized such that Σi= rh E [0, R] for parameter R > 0 [47, 94, 104, 48]. We refer to the setting in which Th E [0 for all h [H), which is the focus of most prior work [70, 72, 71, 67-69, 80), as the dense reward setting, which has R < H; we will frequently specialize our results to this setting.
111.1 Offline Imitation Learning: Behavior Cloning
Let π- = [ : X' + ((A)) denote the expert policy. In the offline imitation learning setting, we receive a dataset D = fo h==
Fi=1 of (reward-free) trajectories of = (æi, ai)....y (I'g diz) obtained by executing x in the underlying MDP M Using these trajectories. our goal is learn policy f such that the rollout regret (TT) - J ( to nt' is as small as possible. We emphasize that π is an arbitrary policy, and is not assumed to be optimal.
Behavior cloning. Behavior cloning, which reduces the imitation learning problem to supervised prediction, is the dominant offline imitation learning paradigm. To describe the algorithm in its simplest form, consider the case where π²" { X' - A} h=1 is deterministic. For user- specified policy class II C {TA, : X + (AA) solves the supervised classification problem ß arg min Σ 1/ I (=)) + ai)) =:
1= the most basic version of behavior cloning [70]
(T). Naturally, other classification losses (e.g., square loss, logistic loss, or log loss) may be used in place of the indicator loss.3 To provide sample complexity bounds for this algorithm, make standard realizability assumption (c.g., Agarwal et al. [2], Foster and Rakhlin [33]).
Assumption 1.1 (Realizability). The policy class II contains the expert policy, i.e. I'' II.
This assumption asserts that Il is expressive enough to represent the expert policy. Depending the application, 1I might be parameterized by simple linear models, or by flexible models such as convolutional neural networks or transformers. We primarily restrict our attention to the realizable setting throughout the paper, as it is meaningful and non-trivial, yet not fully understood. Our main results extend to provide guarantees for the misspecified case, but thorough study of the role of misspecification is beyond the scope of this work. To simplify presentation, we adopt a standard convention in RL theory and focus finite classes with II < 30 [2, 33].
To proceed with analyzing the behavior cloning algorithm, a standard uniform convergence argument > pm (xx) / T (Zx)), then with probability at least
implies that if we define Loe (TT) H
1 6, behavior cloning has
log( 1og(1116-1)
Loo (
Meanwhile, standard error analysis for BC leads to the following bound rollout performance:
J(x)) - J(R) S RH (+).
(1)
'We use the convention that Po(Ø) denotes the initial state distribution.
"To simplify presentation, assume that X' and A are countable, but our results trivially extend to general spaces with an appropriate measure-theoue theoretic treatment.
"Behavior cloning for stochastic expert policies has received limited attention in theory [67], but the logarithmic loss is widely used in practice. One contribution of our work to fill this lacuna.
3

---

Combining these bounds, we conclude that
J(=)) - J(A) RH log(1118-1)
n
For the dense reward setting where R = H, this leads to quadratic dependence on horizon; that is, 22(H2) trajectories are required to achieve constant accuracy. Unfortunately, both steps in this argument are tight in general:
The generalization bound (a) S
is tight even when [II] = 2 (this is true not just for the indicator loss, but for other standard losses such as square loss, absolute loss, and hinge loss). Since the amount of information in a trajectory grows with H, one might hope a- a-priori that the generalization error would decrease with H; alas, this does not occur due to the dependence between samples in each trajectory.
log( (TT
Ross and Bagnell [70] show that the inequality J(x²) - J(T) S RH (+) is tight for MDPs with 3 states; the quadratic scaling in H this induces under dense rewards is often attributed to error amplification or distribution shift incurred by passing from error under the state distribution of n² to the state distribution of म.
Combining, these observations, it is natural to conclude that offline imitation learning is fundamen- tally harder than supervised classification, where linear dependence on horizon might be expected (e.g., with H independent prediction tasks).
1.1.2 Online Imitation Learning and Recoverability
The aforementioned limitations of behavior cloning have motivated online approaches to IL [70, 72, 71, 78]. In the online framework, the learner can interactively choose policies roll out and query the expert for the action at each state in the trajectory (see Appendix E.2 for a formal description), representing a substantially stronger (and in some cases unrealistic) assumption on the learner's 's access both to the MDP and the expert than in the offline setting. Online imitation learning can avoid error amplification and achieve improved dependence on horizon for MDPs that satisfy a recoverability condition [72, 68).
Definition 1.1 (Recoverability parameter). The recoverability parameter for an MDP M* and expert x² is given by*
Under recoverability, the Dagger algorithm of Ross et al. [72] leverages online interaction by inter- actively querying the expert and learning to correct mistakes on-policy, leading to sample complexity
J(TT) - ((T) S WH
(3)
for any finite class 1I and deterministic expert policy म² (for completeness, we include an analysis in Appendix E.2; see Propositions E. and E.2). For the dense reward setting where R = H. we can have f If in the worst case, in which case Eq. (3) matches the quadratic horizon dependence of behavior cloning, but when μ O(1) (informally, this means it is possible to "recover" from a bad action that deviates from π ), the bound in Eq. (3) achieves linear dependence on horizon. Other online IL algorithms such as Forward, Smile [70], and Aggrevate [71] achieve similar guarantees (we are not aware an approach that improves upon Eq. (3) for general finite classes).
The improvements of online II. notwithstanding, Eq. (2) is known be tight for BC, but this is an algorithm-deper dependent (as opposed to information-theoretiee lower bound, and does not preclude the existence of more sample-efficient, purely offline algorithms. In this context, our central question can be restated as: Can offline imitation learning algorithms achieve sub-quadratic horizon dependence for general policy classes II? While prior work has investigated this question for tabular and linear policies [67-69], we approach the problem from new (learning- -theringtth perspective by considering general policy classes.
1.2 Contributions
We present several new results that clarify the role of horizon in offline and online imitation learning.
For stochastic policies, we overload notation and write f(((x)) shorthand for ( [f)).

---

Parameter Sharing (Corollary 2.1)
No Parameter Sharing (1I
111 xl))
(e.g.. [70])
Sparse Rewards
O
R [1I)
O H R 12
Dense Rewards (R = H)
(og((II))
112 log(max [T,,
Table 1: Summary of upper bounds for deterministic experts; lower bounds are more nuanced, and discussed in Section 2.2. Each cell denotes the regret of a policy learned with log-loss behavior cloning (LogLossBC), which is optimal in each setting. Here, IT is the policy class, R is the reward range, H is the horizon, and n is the number of expert trajectories. In the dense-reward setting, we set R H.
1. Horizon-independen analysis of log-loss behavior cloning. Through a new analysis of behavior cloning with the logarithmic loss (LogLossBC), we show that it is possible to achieve horizon-independent sample complexity [47, 94, 104, 105] in offline imitation learning whenever (i) the range of the cumulative payoff's is normalized, and (ii) an appropriate notion of supervised learning complexity for the policy class is controlled. Our result is facilitated by a novel enformation-theorrete analysis which controls policy behavior at the trajectory level, supporting both deterministic and stochastic expert policies.
2. Deterministic policies: Closing the gap between offline and online IL. Specializing LogLossBC to deterministic stationary policies (more generally, policies with parameter sharing) and cumulative rewards in the range [0, H). we show that is possible achieve sample complexity with linear dependence on horizon in offline IL in arbitrary MDPs, matching was was previously only known of online IL. We complement this result with lower bound showing that, without further structural assumptions on the policy class (e.g.. no parameter sharing [67]), online IL cannot improve over offline IL with LogLossBC, even for benign MDPs. Our results are summarized in Table 1. Nonetheless, as observed in prior work [67]. online imitation learning can still be beneficial for non-stationary policies.
3. Stochastic policies:
Tight understanding of optimal sample complexity. For stochastic expert policies, our analysis of LogLossBC gives the first variance-dependent sample complexity bounds for imitation learning with general policy classes, which we prove to be tight in problem-dependent and minimax sense. Using this result, we show that for stochastic stationary experts, (i) quadratic dependence on the horizon is necessary when cumulative rewards lie in the range [0, H). in contrast to the deterministic setting, but (ii) LogLossBBC our variance-dependent analysis-cam sidestep this hardness and achieve linear dependence on horizon under a recoverability-like condition. Finally, we show that-as in the deterministic case-online IL cannot improve over offline IL with LogLossEe without further assumptions on the policy class. Our results are summarized in Table 2.
Toward a thhrning- understanding of imitation learning. Our findings highlight the need to develop fine- grained bebolem-dependent understanding of algorithms and complexity for IL. Instabilities of offline IL [60, 27, 13] and benefits of online IL [73, 52, 38, 6, 26, 51, 7, 108. 59] likely arise in practice, but existing assumptions in theoretical research are often too coarse to give insights into the true nature of these phenomena, leading to an important gap between theory and practice. a first step this direction, we highlight several under-explored mechanisms through which online II. can lead to improved sample complexity, including representational benefits and exploration (Appendix I). We also complement our theoretical results with empirical demonstrations of the phenomena we describe (Appendix C).
Experiments. In Appendix C (deferred the appendix due space constraints), we complement our theoretical results with an empirical demonstration of the porizonninddeeendence of LogLossBC predicted by our theory (under parameter sharing and sparse rewards). We consider tasks where the horizon H can be naturally scaled up and down-foe example, an agent walking for a set number of timesteps and use an expert trained according RL generate expert trajectories, before training a policy using LogLossBC. We consider both continuous action space (MuJoCo environment Walker2d) and discrete action space (Atari environment Beamrider) tasks to demonstrate the broad applicability of our theoretical results. As can be seen in Figure 1, the performance of the learned policy independent or improving with horizon, consistent with our theoretical results. We also perform simplified experiments autoregressive language generation with transformers. Here,
5

---

find that the performance of the imitator is largely independent of H, as predicted by our results, though the results are more nuanced.
Notation. We use I E ( denote the direct delta distribution, which places probability mass on æ. We adopt standard big-oh notation, and write = O(g) to denote that f = Ogg max (1, polylog(g)) and a S b as shorthand for = ((b).
2 Horizon-Independent Analysis of Log-Loss Behavior Cloning
This section presents the first of our main results, crrizzon-indeennden sample complexity analysis of log-loss behavior cloning for the case of deterministic experts, Our second main result, which handles the case of stochastic experts, builds on our results here and is presented in Section 3.
2.1 Log-Loss Behavior Cloning and Supervised Learning Guarantees
The workhorse for all of our results (both for deterministic and stochastic experts) is the following simple modification to behavior cloning. For a class of (potentially stochastic) policies II. we minimize the logarithmic loss:
H ΣV i=1 hm1
n
arg min
log
(aj,
nell
This scheme is ubiquitous in practice [4], and forms the basis for autoregressive language modeling [64]; we refer it LogLossBC. We will show that this seemingly small change- moving from indicator loss to log loss-has significant benefits. Following the classical tradition of imitation learning [70, 72, 71]. our analysis proceeds via reduction supervised learning. We first show that LogLossßa satisfies an appropriate supervised learning guarantee, then translate this into rollout performance. Our starting point is observe that LogL ossBC, via Eq. (4), can be interpreted as performing maximum likelihood estimation over the set {PT] J["" in order to estimate the law IP= over trajectories under x² (see Appendix E. for details). As result, standard guarantees for maximum likelihood estimation [89, 102) imply convergence in distribution whenever x² E II. To be precise, define the squared Hellinger distance for probability measures IP and Q by (P. = (( - d v Then for any finite policy class II, we have the following guarantee."
Proposition 2.1 (Supervised learning guarantee for LogLossBC (special case of Theorem E.1)). For any (potentially stochastic) expert π E I1, the LogLossBC algorithm ensures that with probability at least - D ,,"" < 2 [19[11115
That is, by performing LogLossBC, are implicitly estimating the law p='; note that this result holds even if π- is stochastic, as long n E II. We will focus on finite, realizable policy classes throughout this section simplify presentation as much possible, but guarantees for infinite classes under misspecification are given in Appendix E.
2.2 Horizon-Indepenne
Analysis of LogLossBC for Deterministic Experts
We first consider the case where the expert π is deterministic. Our main result is the following theo- rem, which translates the supervised learning error D3 (TT. (T*,Tx**))) into bound on rollout performance in horizon-independeen fashion.
Theorem 2.1 Glorizon-independerr regret decomposition (deterministic case)). For any deterministic policy nt and potentially stochastic policy f,
J(mT) ((+) < 4R (H(F,
(5)
This result shows that horizon-independent bounds on rollout performance possible whenever (i) rewards are appropriately normalized, and (ii) the supervised learning error D3 (PR .rr)) is appropriately controlled. It is proven using novel crajectory-leve control over deviations between and n we will elaborate upon this in the sequel. We emphasize that this result would be trivial
'While unfamiliar readers might expect a bound on KL divergence, Hellinger distance turns out to be more natural due to connection to the MGF of the log-loss [89, 102). This facilitates scale-free free generalization guarantees in spite of the potential unboundedness of the log-loss..

---

if squared Hellinger distance were replaced by total variation distance in (5); that the bound scales with squared Hellinger distance is crucial for obtaining fast 1/nnttpe rates and linear horizon dependence. We further remark that this reduction is not specific to LogLossBC, and can be applied to any II. algorithm for which we can bound the Hellinger distance. Combining Theorem 2.1 with Proposition 2.1, we obtain the following guarantee for finite policy classes.
Corollary 2.1 (Regret of LogLossBC). For any deterministic expert TI E II, the LogLossBC algorithm in Eq. (4) ensures that with probability at least 1 - J(TT) (T) S 8R
[2
To the best of our knowledge, this is the tightest available sample complexity guarantee for offline imitation learning with general policy classes. This bound improves upon the guarantee for indicator- loss behavior cloning in Eq, (2) by an O(H) factor, and improves upon the guarantee for Dagger in Eq. (3) (replacing H with R S H under т E [0, 1)) in the typical regime where μ !((1).
2.3 Interpreting the Sample Complexity of LogLossBC
To understand the behavior of the bound for LogLossBC in Corollary 2.1 in more detail, we consider two special cases (summarized in Table 1).
Stationary policies and parameter sharing. If log IT| = O(1), the bound in Corollary 2.1 is independent of horizon in the case of sparse rewards (R = (1)), and linear in horizon in the case of dense rewards (R = O(H)). In other words, our work establishes for the first time that:
O(H) sample complexity can be achieved in offline IL under dense rewards for general classes II,
as long as [Tg is appropriately controlled and realizability holds. This runs somewhat counter to intuition expressed in prior work [70, 72, 71, 67-69, 80]. but we will show in the sequel that there is no contradiction.
Generally speaking, we expect to have log|1l| (1) if II consists of stationary policies or more broadly, policies with parameter sharing across steps / E [H] (as is the case in transformers used for autoregressive text generation). As an example, for a tabular (finite state/action) MDP, if II consists of all stationary policies, we have log/II| = | log| so Corollary 2.1 gives J(T))
J(x) < R.X R |o16 ) that is, stationary policies can be learned with horizon- porizon-independent samples horizon under dense rewards. Similar behavior holds for non-stationary policies with parameter sharing log-liog policies of the form (a æ) x exp((on(2) (I, a), 0))); )); see Appendix E. for details.
complexity under sparse rewards and linear dependence
Non-stationary policies or no parameter sharing. For non-stationary policies or policies with no parameter sharing across steps h (e.g., product classes where II II, I12... II)), expect log [I| = (H) (more generally, D3 (Pa pp'') Ö(H/n)). For example, in a tabular MDP, if II consists of all non-stationary policies, we have log [T] H H| log|_Al. In this case, Corollary 2.1
and quadratic dependence on horizon for dense rewards (J(x*) ) (( x H² x log log( 2 ). The latter bound known to be optimal [67] for offline II..
gives linear dependence on horizon for sparse rewards (J(x*) J(R) S
[
2.4 Optimality and Consequences for Online versus Offline Imitation Learning
We now investigate the optimality of Theorem 2.1 and discuss implications for online versus offline imitation learning, well as connections to prior work. Our main result here shows that in the dense-reward regime where Sh. E [0, 1] and R = H, Theorem 2.1 cannot be improved when log [T| = ((1)-even with online access, recoverability, and known dynamics.
Theorem 2.2 (Lower bound for deterministic experts). For any n E N and H E N, there exists (reward-free) MDP M* with |X| = |A| = 2, class of reward functions R with [R] = 2, and a class of deterministic policies II with II| = 2 with the following property. For any (online or offline) imitation learning algorithm, there exists deterministic reward function
}
with Tn E [0, 1] (in particular, R < H) and (optimal) expert policy x* E 11 with μ = 1 such that B[J(=*) - [ Z c- w for an absolute constant e >> O. In addition, the dynamics, rewards, and expert policies are stationary.
Together, Theorems 2.1 and 2.2 show that without further assumptions on II, online imitation learning cannot improve upon offline imitation learning in the realizable setting. That is, even if recoverability
7

---

is satisfied, there is no online imitation learning algorithm that improves upon Theorem 2.1 uniformly for all policy classes. See Appendix H.1 for further lower bounds.
Benefits of online IL for policies with no parameter sharing. How can we reconcile our results with prior work showing that that online IL improves the horizon dependence of offline IL [70. 72, 71, 67-69, 80]? The important distinction here is that online IL can still improve on policy-class dependent basis. In particular, methods like Dagger can still lead to improved sample complexity for policy classes with no parameter sharing across steps h E [H]. Let II, == {TA E II] denote the projection of II onto step h. In Appendix E.2, we prove the following refined guarantee for a variant of Dagger based on the log-lost loss (LogLossDagger).
Proposition 2.2 (Special case of Proposition E.2). When '- E III is determimistic, LogLoss ensures that with probubility at least 1 - 6, -(=t)- ((F)
Σ log( [1, H
- For classes with no parameter sharing (i.e., product classes where IT 11, 1T2
IT)) we have log( (1 " improving on the bound for LogLossBC in Theorem 2.1 by replacing R with μ S R. Thus, online II. can indeed improve over offline II. for classes with no parameter sharing. This is consistent with Rajaraman et al. [67, 68], who proved a μH vs. H²2 gap between online and offline II. for the special case of non-stationary tabular policies (where IT is product class with log/ x H) under dense rewards. However, for classes with parameter sharing (i.e., where log x log([T))
Σ log/II,| = log III In this case, Proposition 2.2 scales as J(TT) J(f) S μ
the bound in Proposition 2.2 scales as HH log|[!] which does not improve over Theorem 2.1 unless u < 1. Since virtually all empirical work on imitation learning uses parameter sharing across steps h E [H], we believe the finding that online II. does not improve over offline II. in this regime is quite salient. Nevertheless, it is important to emphasize that there are various practical considerations (e.g.. misspecification geometric structure) which this result may not account for."
2.5 Proving Theorem 2.1:
How Does LogLossBC Avoid Error Amplification?
The central object in the proof of Theorem 2.1 is the following trajectory-level distance function between policies. For pair of potentially stochastic policies and n², define
p(TT || x²)= == IE" (xr.)))L)) an + d//,l,
(6)
where we use the shorthand d'.H I' (xI..) to indicate that af ~ x'' (=) O'H ~ T (T( We
begin by showing (Lemma F.2) that for all (potentially stochastic) policies n² and म. [(TT) (R)) S
R. p(TT f). We then show (Lemma F.3) that whenever x² is deterministic, Hellinger distance
satisfies? 7 DR (AF, (I".."') )T'' 2 1 p( || =*). Finally, we show (Lemma F.1) that the trajectory-level
distance is symmetric, i.e. p( T²) = -P(T* || f). This step is perhaps the most critical: by considering trajectory-level errors, we can switch from the state distribution induced by से to that of n² for free, without incurring error amplification or spurious horizon factors. Combining the preceding inequalities yields Theorem 2.1; see Appendix F for the full proof.
This analysis closely related to a result in Rajaraman et al. [68]. For the special case of deterministic. linearly parameterized policies with parameter sharing, Rajaraman et al. [68] consider algorithm that minimizes an empirical analogue of the trajectory-wise distance in Eq. (6), and show that leads to a bound similar to Corollary 2.1 (i.e., linear-in-ff sample complexity under dense rewards). Relative to this work, our contributions are threefold: (i) we show that prrizonnindeeendeent sample complexity can be achieved for arbitrary policy classes with parameter sharing, not just linear classes; (ii) we show that said guarantees can be achieved by a natural algorithm, LogLossBC, which is already widely used in practice; and (iii), by virtue of considering the log loss, our results readily generalize to encompass stochastic expert policies, as we will show in the sequel.
3 Horizon-Independee
Analysis of LogLossBC for Stochastic Experts
In this section, we turn out attention to the general setting in which the expert policy s² is stochastic. Stochastic policies are widely used in practice, where they are useful for modeling multimodal behav- ior [76, 25, 14], but have received relatively little exploration in theory beyond the work of Rajaraman
our results, various works show improved horizon dependence in the inverse RL setup where either (i) the MDP dynamics are known, or (ii) the learner can interact with the MDP online, but cannot interact with the expert itself [67. 79]; see Appendix B.
'Complementary
In fact, the opposite direction of this inequality holds as well, up to absolute constant.
8

---

et al. [67] for tabular policies.* 8 Our main result for this section is regret decomposition based on the supervised learning error D ( .Pr')) that is horizon-independent and variance- [107, 106, 93]. To state the result, define o Σx ET [[Q) (I% (x(x)) - Q7 (1 anh =²
as the variance for the expert policy.
Theorem 3.1 (Horizon-independden) independent regret decomposition). tially stochastic) policies 'T" and īn and any E E (0,
Assume R 2 1. For any pair of (poten-
J(x)) - S / 662-
+ ((llog(Re Di F +E.
(7)
Applying this result with LogLossBC leads to the following guarantee.
Corollary 3.1 (Regret of LogLossBC). For any ' E II, the LogLossBC algorithm Eq. (4) ensures that with prob. at least 1 - 5, - J(z) S 0(1)
1oR[ + O(Rlog(n)) (11((1115))
As we show, when the expert policy is stochastic, we can no longer hope for a "fast" 1/n-type rate. and must instead settle for "slow" /n-type rate. The slow term in Corollary 3.1 is controlled by the variance o². for the optimal policy. In particular, if n- is deterministic, then o² = 0, and Corollary 3.1 recovers our bound for the deterministic setting in Corollary 2.1 up to log(n) factor.
3.1 Horizon- ledeeeennndeeeeeenne and Optimality for Stochastic Experts
To understand the dependence on horizon in Corollary 1. we restrict our attention to the "parameter sharing" case where log] II = (1), and separately discuss the sparse and dense reward settings (results summarized in Table 2).
Consider the sparse reward setting where R = O(1.. Here, at first glance it would appear that the variance o². should scale with the horizon. Fortunately, this is not the case: The following result-via law-of-totar Notal-variance-pee type argument [4]- 1i-mmpiles that Corollary 3.1 is fully horizon- independent, with no explicit dependence on horizon when R O(1) and log[IT| O()). For function [T1.HH 01:H), let Var" [f] denote the variance of under (11,a1),... (0 n
Proposition 3.1. We have that oz. S Var"
E rn] S R
For the dense-reward regime where R = H, Proposition 3.1 gives J(TT) ((F) x H (lg(( This is somewhat disappointing, as we now require Ω (2H2) trajectories (quadratic sample complexity) to learn a non-trivial policy, even when logil = O(1). We show now that this quadratic lower bound is qualitatively tight: the slow H/ l//v rate for oz HH2 is necessary in both offline and online IL. This reveals a fundamental difference between deterministic and stochastic experts, since O(H) sample complexity is sufficient in the former case.
Theorem 3.2 (informal). For any o² E [H, H.,, there exists II with III = 2 such that o². S o²
and any (offline or online) IL algorithm must have J(x")- (
with constant probability.
Nonetheless, it is possible to obtain linear-in-Ht H sample complexity for dense rewards under a recoverability-like condition. Let us define the signed recoverability constant via Tú (z, (x)x)) - Q (z, a)]. Note that ğü E [0, and that ğ 2 μ., since this version counts actions that outperform n², not just those that underperform. is immediate to that o2. S T.. Hence, even R H, as long as jı = 0(1), Corollary 3.1 yields J(T')) J(R)
/ log [/n,,, that O H (oog trajectories suffice to learn s-optimal policy."
See Appendix H for further results concerning tightness of Theorem 1.1, including instance-dependent lower bounds.
"s discussed length in Rajaraman al. [67]. many prior works [70, 72] state results in level of generality that allows for stochastic experts, the notions of supervised learning error found these works (c.g., TV distance) do not lead tight rates when instantiated for stochastic experts.
An interesting question for future work is understand if similar conclusion holds if replace with μ.

---

Consequences for online versus offline IL. The lower bound in Theorem G.1 holds even for online imitation learning algorithms. Thus, similar to the deterministic setting, there is no online IL algorithm that improves upon Theorem 3.1 uniformly for all policy classes. This means that even for stochastic experts, online imitation learning cannot improve upon offline imitation learning in the realizable setting without further assumptions (e.g., no parameter sharing) on the policy class under consideration.
When the expert is stochastic, the trajectory-wise distance in Eq. (6), is no longer useful (i.e., p(T* || x²) & 0), which necessitates a more cermmation-theoretii analysis. Our starting point is the following scale-sensitive change-of-measure lemma for Hellinger distance.
Proof sketch for Theorem 3.1.
Lemma 3.1 (Change-of meaaaee meaasree for Hellinger distance [34, 35]). Let IP and Q be probability IR
distributions over measurable space (X, Then for all functions h X
[e(]( - Eg[h(XIII S V (E + (x())(X))) DA Q)
(8)
In particular, if E [0,R) almost surely, then [h()) - 2 Eq [h(X)] + R. (P,
We sketch how to use Lemma 3.1 to prove weaker version of Theorem 3.1, and defer the full proof, which builds on this argument, to Appendix G.1. Define the sum of advantages for trajectory o= = (i),,,),..... (IH,ax) via A(o) = Σ Q7 (In (xx)) - Q (In, an). By the H!
performance difference lemma, we can write [(x=) ((R) E [A)o], so applying Eq. (8) yields
- - - X ET [A()]] + (E _ [A)) + ET [A)())) DJ PT
From here, we observe that E" [A)) 0 and E" (o) = = (this follows because advantages are a martingale difference sequence under |= so all that remains is bound the term E* [A) A crude approach is to observe that |a)) S jHH that applying Lemma 3.1 gives S ET [A] DD (P*, " and consequently J(=*)- S Vo2- (PT This falls short of Eq. (9) due to the suboptimal lower-order term, which does not recover Theorem 2.1 when ' is deterministic (o2. = 0). The full proof in Appendix G.1 corrects this disparity using a sub- tle and significantly more involved argument based on stopping times and martingale concentration.
P )P)
4 Discussion and Additional Results
Our results clarify the role of horizon in offline and online IL, and show that-at least under standard theoretical assumptions the gap between online and offline IL is smaller than previously thought.
Benefits of online interaction Instabilities of offline II. [60, 27, 13] and benefits of online II. [73, 52, 38, 6, 26, 51, 7, 108, 59] likely arise in practice, but existing assumptions in theoretical research on imitation learning appear be too coarse to give insights into the true nature of these phenomena. Toward developing a fine-grained, problem-dependent understanding of algorithms and complexity for IL, in Appendix I, we highlight several special cases in which online interaction does lead to benefits over offline imitation learning, but in a policy class-dependen fashion not captured by existing theory. We identify three phenomena that can lead improved sample complexity: (i) representational benefits; (ii) value-based based feedback; and (iii) exploration.
Further directions. Additional directions for future research include (i) developing and analyzing imitation learning algorithms under -etrrel-theoretcc assumptions that more directly capture practical notions of instability [61, 88, 13, 14], and (ii) developing a more refined theory in the context of language models, via the connection in Appendix B.3. For both settings, important question is to understand whether the notion of supervised learning error D (F# . consider is suitable proxy for real-world performance, or whether more refined notions are required.
Additional results. Secondary results deferred to the appendix for space include (i) examples and additional guarantees for LogLossBC and LogLossDagger (Appendix E); and (ii) additional lower bounds and results concerning the tightness of Theorems 2.2 and 3.1 (Appendix H).
10

---

Acknowledgements
We thank Jordan Ash, Audrey Huang, Akshay Krishnamurthy, Max Simchowitz, and Cyril Zhang for many helpful discussions. We thank Drew Bagnell for valuable comments and pointers to related work.
References
[1] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, page I, 2004.
[2] A. Agarwal, N. Jiang, and S. M. Kakade. Reinforcement learning: Theory and algorithms. 2019.
[3] A. Ayoub, K. Wang. Liu, S. Robertson, J. McInemny, D. Liang, N. Kallus, and C. Szepesvári. Switching the loss reduces the cost in batch reinforcement learning. arXiv preprint arXiv:2403.05383 2024.
[4] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272, 2017.
[5] G. Bachmann and V. Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06965 2024.
[6] M. Bansal, A. Krizhevsky, and A. Ogale. Chauffeurnet: Learning to drive by imitating the best and synthesizing the worst. arXiv preprini arXiv: 18/2.03079 2018.
[7] M. Barnes. World scale inverse reinforcement learning in Google Maps. https:// google/blog/ hat.l///loowwwrldddeeeeee 2023. [Online; accessed 26 26-0ct-2024).
maps/
[8] P. L. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-norrmaizzed margin bounds for neural networks. In Advances in Neural Information Processing Systems, 2017.
M. G. Bellemare, Y. Naddaf, Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253 279, 2013.
[10] A. Beygelzimer, Dani, T. Hayes, J. Langford, and B. Zadrozny. Error limiting reductions between classification tasks. In Proceedings of the 22nd international conference Machine learning, pages 49-56, 2005.
[11] A. Beygelzimer, J. Langford, I.. Li, L.. Reyzin, and R. Schapire. Contextual bandit algorithms with supervised learning guarantees. Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 19-26, 2011.
[12] S. Bhattamishra, K. Ahuja, and Goyal. On the ability and limitations of transformers to recognize formal languages, In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096-7116. 2020.
[13] A. Block, D. J. Foster, A. Krishnamurthy, M. Simchowitz, and C. Zhang. Butterfly effects of sgd noise: Error amplification in behavior cloning and autoregression. International Conference on Learning Representations (ICLR), 2024.
[14] A. Block, A. Jadbabaie, D. Pfrommer, M. Simchowitz, and R. Tedrake. Provable guarantees for generative behavior cloning: Bridging lew-level stability and high-level behavior. Advances in Neural Information Processing Systems, 36, 2024.
[15] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, and J. Zhang. End to end learning for self-driving cars. arXiv preprint /rxiv::604 0tt.///044.011666 07316, 2016.
[16] Brantley, W. Sun, and M. Henaff. disagreement-reguuariiee imitation learning. Interna- tional Conference Learning Representations, 2019.

---

[17] M. Braverman, X. Chen, S. Kakade, K. Narasimhan, C. Zhang, and Y. Zhang. Calibration, entropy rates, and memory in language models. In International Conference on Machine Learning, pages 1089-1099. PMLR, 2020.
[18] C. L. Canonne. A short note on learning discrete distributions. arXiv:2002.114577 2020.
arXiv preprint
[19] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA, 2006. ISBN 0521841089.
[20] J. D. Chang, M. Uchara, D. Sreenivas. R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data without great coverage. Advances Neural Information Processing Systems, 2021.
[21] J. D. Chang, K. Brantley, R. Ramamurthy, D. Misra, and W. Sun. Learning to generate better than your 1mm. arXiv preprint arXiv:2306. 1816, 2023.
[22] C.-A. Cheng and Boots. Convergence of value aggregation for imitation learning. In International Conference on Artificial Intelligence and Statisties, pages 1801-1809. PMLR, 2018.
[23] C.-A. Cheng, Yan, E. Theodorou, and B. Boots. Accelerating imitation learning with predictive models. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3187-3196. PMLR, 2019.
[24] C.-A. Cheng, A. Kolobov, and A. Agarwal. Policy improvement via imitation of multiple oracles. Advances in Neural Information P Processing Systems, 33:5587-5598, 2020.
[25] 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.0413 2023.
[26] S. Choudhury, M. Bhardwaj, Arora, Kapoor, Ranade, Scherer, and D. Dey. Data- driven planning via imitation learning. The International Journal of Robotics Research, 37
(13-14):6332-167, 2018.
[27] P. De Haan, D. Jayaraman, and S. Levine. Causal confusion imitation learning. Advances in neural information processing systems, 32, 2019.
[28] D. L. Donoho and R. C. Liu. Geometrizing rates of convergence, II. The Annals of Statistics, pages 633-667, 1991.
[29] J. Farebrother, J. Orbay, Q. Vuong, A. Taiga, Chebotar, T. Xiao, A. Irpan, S. Levine, Castro, and A. Faust. Stop regressing: Training value functions via classification for scalable deep rl. arXiv preprini arXiv:2403.03950 2024.
[30] Finn, T. Yu, T. Zhang, Abbeel, and Levine. One-shot visual imitation learning via meta-learning. In Conference robot learning, pages 357-368. PMLR, 2017.
[31] P. Florence, C. Lynch, A. Zeng, O. A. Ramirez, A. Wahid, L. Downs, A. Wong, J. Lee, I. Mordatch, and J. Tompson. Implicit behavioral cloning. In Conference on Robot Learning, pages 158-168. PMLR, 2022.
[32] D. J. Foster and A. Krishnamurthy. Efficient first-order contextual bandits: Prediction, al- location, and triangular discrimination. Neurul Information Processing Systems (NeurIPS), 2021.
[33] J. Foster and A. Rakhlin. Foundations of reinforcement learning and interactive decision making, arXiv preprint arXiv:2312.167300 2023.
[34] D. J. Foster, M. Kakade, Qian, and Rakhlin. The statistical complexity of interactive decision making, arXiv preprint arXiv:2112.13485 2021.
[35] D. J. Foster, A. Rakhlin, A. Sekhari, and K. Sridharan. On the complexity of adversarial decision making. Advances Neural Information Processing Systems, 35:35404-35417, 2022.
12

---

[36] J. J. Foster, Y. Han, J. Qian, and A. Rakhlin. Online estimation via offline estimation: An coormation-theoredee framework. arXiv preprint arXiv:2404.10122, 2024.
[37] N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-2999 2999. PMLR, 2018.
[38] S. Gupta, Davidson, S. Levine, R. Sukthankar, and Malik. Cognitive mapping and planning for visual navigation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2616-2625, 2017.
[39] M. Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
[40] S. Hanneke. Theory of disagreement- active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-333 2014.
[41] A. Havens and B. Hu. On imitation learning of linear control policies: Enforcing stability and robustness constraints via Imi conditions. 2021 American Control Conference (ACC), pages 882-887. IEEE, 2021.
[42] J. Ho and S. Ermon. Generative adversarial imitation learning, Advances in neural information processing systems, 29, 2016.
[43] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. arXiv preprint 1XXv::99440095/11 2019.
[44] Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: survey of learning methods. ACM Computing Surveys (CSUR), 50(2): 2017.
[45] A. Hussein, E. Elyan, M. M. Gaber, and C. Jayne. Deep imitation learning for 3d navigation tasks. Neural computing and applications, 99:389-404, 2018.
[46] B. Ibarz, J. Leike, T. Pohlen, G. Irving, S. Legg, and D. Amodei. Reward learning from human preferences and demonstrations in atari. Advances in neural information processing systems, 31, 2018.
[47] N. Jiang and A. Agarwal. Open problem: The dependence of sample complexity lower bounds on planning horizon. In Conference On Learning Theory, pages 3395-3398. PMLR, 2018.
[48] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Neural Information Processing Systems, 2021.
[49] L. Ke, S. Choudhury, M. Barnes, W. Sun, G. Lee, and S. Srinivasa. Imitation learning as f-divergence minimization. In Algorithmic Foundations of Robotics XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics 14, pages 313-329. Springer, 2021.
[50] L. Ke, J. Wang. T. Bhattacharjee, B. Boots, and S. Srinivasa. Grasping with chopsticks: Combating covariate shift in model-free imitation learning for fine manipulation. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 6185-6191. IEBE, 2021.
[51] M. Kelly, C. Sidrane, K. Driggs-Campbell 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.
[52] B. Kim, A.-m. Farahmand, J. Pineau, and D. Precup. Learning from limited demonstrations. Advances in Neural Information Processing Systems, 26, 2013.
[53] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
[54] M. Laskey, Lee, R. Fox, A. Dragan, and K. Goldberg. Dart: Noise injection for robust imitation learning. In Conference robot learning, pages 143-156. PMLR, 2017.
13

---

[55] Y. LeCun. Do large language models need sensory grounding for meaning and understanding. In Workshop on Philosophy of Deep Learning. NYU Center for Mind, Brain, and Consciousness and the Columbia Center for Science and Society, 2023.
[56] Y. Li and C. Zhang. On efficient online imitation learning via classification. Advances in Neural Information Processing Systems, 35:32383-323 -33397,, 2022.
[57] Y. Li, J. Song, and S. Ermon. Infogail: Interpretable imitation learning from visual demonstra- tions. Advances in neural information processing systems, 30, 2017.
[58] Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shorteuts to automata. In The Eleventh International Conference Learning Representations, 2022.
[59] T. G. W. Lum, M. Matak, V. Makoviychuk, A. Handa, A. Allshire, T. Hermans, N. D. Ratliff, and K. Van Wyk. Dextrah-g: Pixels-to-action dexterous arm-hand grasping with geometric fabries. arXiv preprint ar arXiv:2407 .22000 2024.
[60] U. Muller. Ben, E. Cosatto, B. Flepp. and Y. Cun. Off-road obstacle avoidance through end-to-end learning. Advances in neural information processing systems, 18, 2005.
[61] D. Pfrommer, T. Zhang. S. Tu, and N. Matni Tasil: Taylor series imitation learning. Advances in Neural Information Processing Systems, 35:20162 15:20112-20174, 2022.
[62] Y. Polyanskiy and Y. Wu. Lecture notes on information theory. 2014.
[63] D. A. Pomerleau. Alvinn: An autonomous land vehicle in neural network. Advances in neural information processing systems, 1988.
[64] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, (8)99, 2019.
[65] Raffin. RI baselines3 zoo. httpss//ggtthub..co////R//////// wttp://cc///oo////_..
2020.
[66] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann. Stable-baselines:: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22 (268):1-8, 2021. URL http: j/mlr//mmrr////// org/ prggpppprss/222220010 3364.htm..
[67] N. Rajaraman, L. Yang. J. Jiao, and K. Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 33:2914-2992 2020.
[68] N. Rajaraman, Y. Han, L. Yang. J. Liu, J. Jiao, and Ramchandran. On the value of interaction and function approximation in imitation learning. Advances in Neural Information Processing Systems, 34:1325-1333 1336, 2021.
[69] N. Rajaraman, Y. Han, L. F. Yang. K. Ramchandran, and J. Jiao. Provably breaking the quadratic eиror compounding barrier in imitation learning, optimally, arXiv preprint 102. 2021.
[70] S. Ross and D. 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.
[71] S. Ross and J. A. Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5977 2014.
[72] S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured predic- tion no-regret online learning. In Proceedings of the fourleenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
[73] S. Ross, N. Belik-Barkhudarov,
Shankar, A. Wendel, D. Dey, A. Bagnell, and M. Hebert. Learning monocular reactive uav control in cluttered natural environments. In 2013 IEEE international conference on robotics and automation, pages 1765-1772. IEEE, 2013.
14

---

[74] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 2017.
[75] A. Sekhari, K. Sridharan, W. Sun, and R. Wu. Selective sampling and imitation learning via online regression. Advances in Neural Information Processing Systems, 36, 2024.
[76] N. M. Shafiullah, Z. Cui, A. A. Altanzaya, and L. Pinto. Behavior transformers: Cloning modes with one stone. Advances in neural information processing systems, 15:22955-22966 2022.
[77] J. Spencer, S. Choudhury, A. Venkatraman, B. Ziebart, and J. A. Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint arXiv:2 202.200200000 02872, 2021.
[78] W. Sun, A. Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning, pages 3309-331. PMLR, 2017.
[79] G. Swamy, S. Choudhury, J. A. Bagnell, and S. Wu. Of moments and matching: A game- theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pages 10022-10032. PMLR, 2021.
[80] G. Swamy, N. Rajaraman, M. Peng. S. Choudhury, J. Bagnell, S. Z. Wu, Jiao, and K. Ram- chandran. Minimax optimal online imitation learning via replay estimation. Advances in Neural Information Processing Systems, 35:7077-7000 -088, 2022.
[81] U. Syed and R. E. Schapire. A thee-the approach to apprenticeship learning. Advances neural information processing systems, 20, 2007.
[82] U. Syed and R. E. Schapire. A reduction from apprenticeship learning to classification. Advances in neural information processing systems, 23, 2010.
[83] U. Syed, M. Bowling, and R. E. Schapire. Apprenticeship learning using linear programming. In Proceedings of the 25th international conference Machine learning, pages 1032-1039, 2008.
[84] D. Tiapkin, D. Belomestny, D. Calandriello, E. Moulines, A. Naumov, P. Perrault, M. Valko, and Menard. Demoostration-rggulaiizdd rl. International Conference on Learning Repre- sentations, 2024.
[85] E. Todorov, Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033. IEEE, 2012. doi: 00.1109//OSS.2112.666611
[86] M. Towers, J. K. Terry, A. Kwiatkowski, J. U. Balis, G. d. Cola, T. Deleu, M. Goulão, A. Kallinteris, A. KG, M. Krimmel, R. Vicent,, A. Pierré, S. Schulhoff, J. J. Tai, A. T.J. Shen, and O. G. Younis. Gymnasium, Mar. 2023. URL https:://zenntt org/record/ 8127025.
[87] S. Tu, R. Frostig, and M. Soltanolkotabi. Learning from many trajectories. arXiv preprint arXiv:2203.17193, 2022.
[88] S. Tu, A. Robey, Zhang, and Matni, On the sample complexity of stability constrained imitation learning. In Learning for Dynamics and Control Conference, pages 180-191. PMLR, 2022.
[89] S. A. van de Geer. Empirical Processes in M-Estimation, Cambridge University Press, 2000.
[90] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, Georgiev, et al. Grandmaster level in starcraft using multi-agent reinforcement learning. Nature, 57507782):5003344 2019.
[91] M. J. Wainwright. High-dimensional statisties: non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
15

---

[92] K. Wang, K. Zhou, R. Wu, N. Kallus, and W. Sun. The benefits of being distributional: Small-loss bounds for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
[93] K. Wang, O. Oertell, A. Agarwal, N. Kallus, and W. Sun. More benefits of being distributional: Second-order bounds for reinforcement learning. arXiv preprint arXiv:2402.07 22224000....,, 2024.
[94] R. Wang. S. S. Du, L. F. Yang, and S. M. Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? Neural Information Processing Systems (NeurIPS), 2020.
[95] K. Wen, Y. Li, B. Liu, and A. Risteski. Transformers are uninterpretable with myopic methods: a case study with bounded dyck grammars. Advances in Neural Information Processing Systems, 36, 2024.
[96] D. Williams. Probability with martingales. Cambridge university press, 1991.
[97] W. H. Wong and X. Shen. Probability inequalities for likelihood ratios and convergence rates of sieve mles. The Annals of Statistics, pages 339-362, 1995.
[98] T. Xu, Z. Li, Y. Yu, and Z.-Q. Luo. Understanding adversarial imitation learning in small sample regime: A stage-coupled analysis. arXiv preprini arXiv:2208.0188:: 2022.
[99] X. Yan, B. Boots, and C.-A. Cheng. Explaining fast improvement in online imitation learning. In Uncertainty in Artificial Intelligence, pages 1874-1884, PMLR, 2021.
[100] S. Yao, B. Peng, C. Papadimitriou, and K. Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Associa- tion for Computational Linguistics and the I 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 3770-3785, 2021.
[101] A. Zanette and E. Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7312-7312. PMLR, 2019.
[102] T. Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):2180-25 2006.
[103] T. Zhang, Z. McCarthy, O. Jow, D. Lee, X. Chen, K. Goldberg, and Abbeel. Deep imitation learning for complex manipulation tasks from virtual reality teleoperation. In 2018 IEEE international conference on roboties and automation (ICRA), pages 5628-5635. IEEE, 2018
[104] Z. Zhang, X. Ji, and S. Du. Is reinforcement learning more difficult than bandits? near- optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR, 2021.
[105] Z. Zhang, X. Ji, and S. Du. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. In Conference Learning Theory, pages -35444 PMLR, 2022.
[106] H. Zhao, J. He, D. Zhou, T. Zhang, and Q. Gu. Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory, pages 4977-5020. PMLR, 2023.
[107] R. 7hou, Z. Zihan, and S. Du. Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments. In International Conference on Machine Learning, pages 42878-427 42914. PMLR, 2023.
[108] Z. Zhuang, Z. Fu, J. Wang, C. Atkeson, S. Schwertfeger, C. Finn, and H. Zhao. Robot parkour learning. arXiv preprint arXiv:2309.000 200.00666566 2023.
[109] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforce- ment learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008
16

---

Contents of Appendix
Omitted Tables
18
Additional Related Work
18
B.1
Theory of Imitation Learning and Reinforcement Learning
18
B.2
Empirical Research on Imitation Learning
19
B.3
Autoregressive Language Modeling
20
C Experiments
20
C.I Experimental Setup
20
C.2 Results
23
Technical Tools
25
D.1
Tail Bounds
25
D.2
Information Theory
................................
26
D.3
Reinforcement Learning
26
D.4 Maximum Likelihood Estimation
27
I Proofs and Supporting Results
28
E Examples and Supporting Results from Section 2 and Section 3
28
E.I General Guarantees and Examples for Log-Loss Behavior Cloning
28
E.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger
31
F Proofs from Section 2
34
F.1 Proof of Theorem 2.1
F2 Proof of Theorem 2.2
36
G Proofs from Section 3
37
G.1 Proof of Theorem 3.1
................................
37
G.2 Formal Statement and Proof of Theorem G.I
................................
44
G.3 Additional Proofs
46
II Additional Results
47
H Additional Lower Bounds
47
H.1
Lower Bounds for Online Imitation Learning in Active Interaction Model An Instance-Dependen Lower Bound for Stochastic Experts Tightness of the Hellinger Distance Reduction
47
H.2
49
H.3
I
Benefits of Online Interaction
53
I11
The Role of Misspecification
53
I.2
Representational Benefits
53
I.3
Benefits of Value-Based Feedback
54
1.4
Benefits from Exploration
55
1.5
Proofs
55
17

---

A Omitted Tables
Worst-case
Low-noise
p-recoverable
Sparse
(
N/A
Rewards
Rewards
Dense
H
logtlT
log(
(og(
PV
H (lgg(( #f (TT)
Table 2: Summary of upper bounds for stochastic experts (Corollary 3.1). Each cell denotes the expected regret of a policy learned with LogLossBC; lower bounds are more nuanced and discussed in Section 3. Here II is the policy class, R is the cumulative reward range, H is the horizon, n is the number of expert trajectories, of. is the variance of the expert policy, and ji is the signed recoverability parameter see Section for definitions." 10
B Additional Related Work
B.1
Theory of Imitation Learning and Reinforcement Learning
Classical theoretical works in imitation learning, beginning from the work of Ross and Bagnell [70] observes that behavior cloning (for the specific indicator loss in Section 1.1) can incur quadratic dependence horizon, and shows that online interaction, via algorithms like Dagger and Aggrevate, can obtain improved sample complexity under recoverability-yye conditions [70, 72, 71, 78J. Further works along this line include Cheng and Boots [22], Cheng et al. [24, 23], Yan et al. [99], Spencer et al. [77].
These papers can be thought of as supervised learning reduction, in the sense that-in the vein of Eq. (hyythey guarantee that the imitation learning performance is controlled by an appropriate notion of supervised learning performance. Notably, this holds for any policy म. which means that in practice, the rollout performance good whenever supervised learning succeeds, even if we do not necessarily have a provable guarantee for the generalization of î (e.g., for neural networks, where understanding generalization an active area of research). However, as noted throughout this paper and elsewhere [67-69], these works typically state regret guarantees in terms of different, often incomparable notions of supervised learning performance, and avoid giving concrete, end-to-end guarantees for specific policy classes of interest. This can make it challenging to objectively evaluate optimality, and understand whether limitations of specific algorithms are due to suboptimal design choices versus cnpommtioonthhoretti limitations. For example, Li and Zhang [56] show that in some cases, supervised learning oracles that satisfy assumptions required by prior work do not actually exist.
Minimax sample complexity of imitation learning. More recently, a line of work beginning with Rajaraman et al. [67] revisits the minimax sample complexity of imitation learning, aiming to provide end-to-end sample complexity guarantees and lower bounds, but primarily focused on tabular MDPs and policies [67-69, 80]. Notably, Rajaraman al. [67] show that when 1I is the set of all non-stationary policies in a tabular MDP and = H. online IL methods can achieve (wll) sample complexity, while offline IL methods must pay S?(H²)); this is consistent with our findings in Section 2, as log = S2H)) for this setting. Other interesting findings from this line of work include the observation that when the MDP dynamics
known, the sample complexity for offline II. with non-stationary tabular policies can be brought down to O(H3/2). As noted in Section 2, Rajaraman et al. [68] show that offline IL methods can obtain O(H) sample complexity for linearly parameterized policies under parameter sharing; our analysis of ossLosBCC for the special case of deterministic policies shows that it can be viewed as implicitly minimizing the objective they consider.
Xu et al. [98] also consider the problem horizon independence in II., Their work focuses on tabular MDPs and policies, and shows with knowledge of the dynamics, it is possible to achieve horizon dependence for a restricted class of MDPs termed RBAS-MDPS In contrast, our work achieves horizon independence for general MDPs, without knowledge of dynamics.
Compared to the works above, we focus on general finite classes II. Various works on theoretical reinforcement learning [2, 33] have observed that finite classes are a useful test case for general function approximation, because they arguably the simplest type of policy class from generaliza-
18

---

tion perspective, yet do not have any additional structure (e.g., linearity) that could lead to spurious conclusions that do not extend rich function classes like neural networks.
Recent work of Tiapkin et al. [84] provides generalization guarantees for behavior cloning with the logarithmic loss, but their results scale linearly with the horizon, and thus cannot give tight guarantees for policy classes with parameter sharing. In addition, their results are stated in terms of KL-divergence and, as a consequence, require a lower bound on the action densities for the policy class under consideration. We expect that both of these limitations are inherent to KL divergence. Tiapkin et al. [84] also give variance- deeendddd bounds on rollout performance similar to Theorem 3.1, but their results require a bound on KL divergence (which is stronger than a bound on Hellinger distance), and thus are unlikely to meaningfully capture optimal horizon dependence. These bounds on rollout performance also do not recover the notion of variance in Theorem 3.1.
We also mention in passing Sekhari et al. [75], who consider active imitation learning algorithms, and focus on obtaining improved sample complexity with respect to dependence on the accuracy (as opposed to H). under strong distributional assumptions in the vein of active learning [40].
Inverse reinforcement learning. A long line of research on inverse reinforcement learning and related techniques considers a setting in which either a) the dynamics of the MDP M* are known, or b) it is possible to interact with MM online (without expert feedback), with empirical [1, 109] and theoretical results [81, 83, 82, 16. 20J. This setting encompasses generative adversarial imitation learning and related moment matching methods [42, 57, 49, 79J. A detailed discussion is out of scope for the present work, but we believe this framework can improve over the sample complexity of offline IL in some but not all situations (e.g.. Rajaraman et al. [67]).
Benefits of logarithmic loss. Our work draws inspiration from Foster and Krishnamurthy [32], who observed that the logarithmic loss can have benefits over square loss when outcomes are heteroskedastic, and used this observation to derive first-order regret bounds for contextual bandits. Subsequent works have extended their analysis technicals to derive first-order regret bounds in various reinforcement learning settings [92, 93, 3]. 11 To the best of our knowledge, our work the first to uncover a decision making setting in which switching to the logarithmic loss is beneficial even in a minimax sense. We emphasize that while our analysis uses the information-the -theoretic machinery introduced in Foster and Krishnamurthy [32] and related work [34, 35], our results are quite specialized structure of the imitation learning setting, and cannot directly be derived from any of the results in Foster and Krishnamurthy [32], Wang et al. [92, 93], Ayoub et al. [3].
Horizon-free reinforcement learning. Our results also take inspiration from the line of research on horizon-independer sample complexity bounds for reinforcement learning [47, 101, 94, 104, 105], as well as a closely related line of research on variance-dependent regret bounds [107, 106, 93]. These papers provide sample complexity bounds for reinforcement learning that have little or no explicit dependence on horizon whenever rewards are normalized such that Σ Th E 00 1]. We consider simpler setting (imitation learning), but provide guarantees that hold under general function approximation, while the works above are restricted to either tabular MDPs or MDPs with linear/low- rank structure. Nonetheless, our proof of Theorem 3.1 makes use of concentration arguments inspired by Zhang et al. [104, 105].
B.2 Empirical Research on Imitation Learning
Many empirical works have observed compounding error in behavior cloning. Outside of online imitation learning. mitigations include noise injection at data collection time [54, 50] or inverse RL methods that assume knowledge of system dynamics [109]. Other works take a control-theoretio perspective [88, 41, 61, 14], and augment behavior cloning with techniques designed to ensure incremental stability (or other control-theoreti notions of stability) of system.
Online imitation learning. Many empirical works have noted benefits of online imitation learning methods like Dagger over classical behavior cloning [73, 52, 38, 6, 26, 51, 7, 108, 59]. These results are not in contradiction to our findings, as they typically do not ablate the effect of the loss function
We also mention in passing the work of Farebrother et al. [29], which observes that switching to the log-loss is beneficial empirically for approximate value iteration methods in offline reinforcement learning. 'CCompared to variance-deppe dependen bounds for RL in Zhou et al. [107]. Zhao et al. [106]. Wang et al. [93] an interesting feature of Theorem 3.1 is that it only depends on variance for x'' whereas these works typically depend on worst-case variance over all policies or similar quantities.
19

---

(e.g., [70] uses the squared hinge loss, Ross et al. [72] uses the hinge loss, and Ross et al. [73] uses the square loss). It is also possible that the perceived benefits arise from factors beyond horizon (e.g.. representational benefits), as discussed in Appendix I.
B.3 Autoregressive Language Modeling
Autoregressive language modeling with the standard next-token prediction objective [64] can be viewed an instance of behavior cloning with the logarithmic loss. In this setting, M corresponds to a token-level MDP. Here A is a space or vocabulary of lokens The initial state is #j = 2 ~ Po. where 2 is a prompt or context. Given the prompt, for each I..... H the action On E A is new token, which is concatenated to the state via the deterministic dynamics 24+1 & (2, (1.k) Via Bayes' rule, an expert policy
H
ा (a1.H 12) = II T 2
2.01
II
क (ap (b))
A=1
can represent an arbitrary conditional distribution over sequences, from which training set D {0'} with o' (2', ai....,,ūp ) is generated. With this setup, log-loss behavior cloning
12
H
ΣΣ log(Tn (aj, 2² 11)
arg Max Tell
is equivalent to the standard next-token prediction objective for unsupervised language model pre- training [64], with the class parameterized by a transformer or a similar neural net architecture. In amplification arising from the next-token prediction objective (often referred to as exposure bias) has been widely observed by prior work [43, 17, 13], and in some cases speculated to be fundamental limitation [55, 5].
this context, long-range
Applying our results. To apply our results, consider a fixed reward function r = {ra)en which might measure performance for particular task of interest (e.g., question answering commonsense reasoning). Then, for a model I, J(r) corresponds to rollout performance at the task for an autoregressively generated sequence (i.e., given ~ Po. we sample an Tx(- 2,01-11) for all E [H). For this setting, Theorem 3.1 states that
J(x*) - J( & δ (V (i( + R "R("",Pr)) )
(9)
where o². - - ET [(QT (z, (1:h) (1t V. (z. 11) In particular, as long as the cumula- tive reward for the task is bounded by R 0(1) (e.g., if we receive an episode-level reward r' 1 if a question is answered correctly, and receive zero reward otherwise), the rollout performance has no explicit dependence on the sequence length, except through the generalization error D3 (IP², p=*) ). In light of this result, expect that error amplification observed in practice may arise from challenges in minimizing the generalization error D2 (Pa P=' itself (e.g., architecture, data generation process, optimization [17, 13J), rather than fundamental limits next-token prediction.
C Experiments
In this section, we validate our theoretical results empirically. We first provide a detailed overview of our experimental setup, including the control and natural language tasks we consider, then present empirical results for each task individually. We ran all of our experiments on NVidia V100 GPUs. Training time for each experiment varied by environment, but all were less than hours.
C.1 Experimental Setup
We evaluate the effect of horizon the performance of LogLossBC in three environments. We begin by describing our training and evaluation protocol (which is agnostic to the environment under consideration), then provide details for each environment.
In each experiment, we begin with an expert policy x² (which is always a neural network; details below) and construct offline dataset by rolling out with it times for H timesteps per episode. To train the imitator policy म, we use the same architecture as the expert, but randomly initialize the weights and use stochastic gradient descent with the Adam optimizer minimize the LogLossBC
20

---

MuJoCo
Atari
0.30
0.10
Expected Rlggre.
0.05
trajectorin 13 trajectories
Expected Regret.
trajectorie
0.20
10 rrjectones
0.00
srojctiones 50 tryretonies
50 rnyectories
0.15
120 trajector
trajecturne 530 trajector et
trajector
-0.05
0.10
0.05
400
Horizon
Horizon
(a)
(b)
Figure 2: Dependence of expected regret on the horizon for multiple choices for the number of imitator trajectories n. (a) Continuous control environment Walker2d-v4. (b) Discrete Atari environ- ment BeamidenNoorrmmekiivv. For both environments, increasing the horizon does not lead to a significant increase in regret, as predicted by our theory.
objective for the offline dataset; this setup ensures that the realizability assumption used by our main results (Assumption 1.1) is satisfied. We repeat this entire process for varying values of H.
To evaluate the regret J(x*) - (()) after training, we approximate the average reward of the imitator policy î by selecting random seeds and collecting trajectories of length H by rolling out with ;; we approximate the average reward of the expert n* in the same fashion, and we also compute several auxiliary performance measures (details below) that aim to capture the distance between स and x² In all environments, we normalize rewards so that the average reward of the expert is at most 1, in order to bring to the sparse reward setting in Section 1.1 and keep the range of the possible rewards constant as a function of the (varying) horizon.
We consider four diverse environments, with the aim of evaluating LogLossBC in qualitatively different domains: (i) Walker2d, classical continuous control task from MuJoCo [86, 85] where the learner attempts make stick fguur--ikee agent walk to the right by controlling its joints; (ii) Beamrider, a standard discrete-action RL task from the Atari suite [9], where the learner attempts to play the game of Beamrider; (iii) Car, top-down discrete racing environment where the car has to avoid obstacles to reach a goal, and (iv) Dyck, an autoregressive language generation task where the agent is given sequence of brackets in (6),6),)) and has close all open brackets in the correct order.
We emphasize diversity in task selection in order to demonstrate the generality of our results, covering discrete and continuous actions spaces, as well as both control and language generation. For some of the environment (Walker2d, Beamrider), the task is intended to be "stateless", in the sense that varying the horizon H does not change the difficulty of the task itself (c.g.. complexity of the expert policy x),, allowing for honest evaluation of the difficulty of the learning problem we vary the horizon H. For other domains, such as Dyck, horizon dependence is more nuanced, as here the capacity required to represent the expert grows the horizon increases; this manifests itself in our theoretical results through the realizability condition (Assumption 1.1), which necessitates a more complex function class II H increases.
We now provide details for our experimental setup for each environment.
Walker2d. We use the Gymnasium [86] environment Walker2d-v4, which has continuous state and action spaces of dimensions 17 and 6 respectively. The agent is rewarded for moving to the right and staying alive well as being penalized for excessively forceful actions; because we vary the horizon H, in order to make the comparison fair, we normalize the rewards so that our trained expert always has average reward 1. Our expert is a depth-2 MLP with width 64. We use the Stable- Stable-Baselines3 3aselines3 [66] implementation of the Proximal Policy Optimization (PPO) algorithm [74] with default settings to train the expert for 500K steps. The policy's 's action distribution Gaussian, with the mean and covariance determined by the MIP; we use this for computation of the logarithmic loss. For data collection, we enforce a deterministic expert by always playing the mean of the Gaussian distribution produced by their policy. Our imitator policy uses the same architecture the expert policy, with the
21

---

Dyck Language
Log Norm
1.0
hariman 20
0.8
horizon
Expeceed Regret
1.2
0.6
1.1
0.4
0.2
0.9
0.0
2000
4000
6000
8000
10000
10
20
Number of Trajectorics
Horizon
(a)
(b)
Figure 3: (a) Relationship between the number of expert trajectories and expected regret for the Dyck environment multiple choices of horizon H. The expert is trained to produce valid Dyck words of length H, and the imitator's s ability to generate valid word evaluated. We find that regret increases as function of H. (b) Logarithm of the product of weight matrix norms for the expert policy network as a function of H, for Dyck and Car environments. The Dog-product-nomm acts as a proxy for complexity for the class IT; we rescale such that log- sgg-product-nomn at H 10 is 1.0 for both domains. For Dyck, we find that as H increases, the complexity of IT required to represent the expert policy (as measured by the log-product-normi also increases, explaining the increasing regret in (a). However, the gain in log-product-nome for the Car domain is much lower, which is in line with the fact that the regret for the Car domain exhibits only mild scaling with horizon.
weights re- re-initialized randomly. We train the imitator using the logarithmic loss by default, but an ablation, we also evaluate the effect of training with the mean- sean---uared-erro loss on the Euclidean norm over the actions. We train using the Adam optimizer [53] with learning rate of 10-3 and batch size of 128. We stop training early based on the validation loss on held out set of expert trajectories. Note that the expert and imitator policies above both stationary policies.
Beamrider. We use the Gymnasium environment BeamRidenNoFramessiivv. which has 9 discrete actions and a 210x160x3 image as the state; the rewards are computed as a function of how many enemies are destroyed. As in the case of the previous setup, we account for the varying of H by normalizing expert rewards to be 1. Here we do not train our expert ourselves, but instead use the trained PPO agent provided by Raffin [65], which a convolutional neural network. We use the same architecture for our imitator policy, with the weights re- re-initialized randomly. Here, the expert (and imitator) policies map the observation to a point on the probability simplex over actions, and so logarithmic loss computation is immediate. Similar to the case of Walker2d, we enforce deterministic expert for collecting trajectories by taking the action with maximal probability. We then train our imitators using the same setup as in the Walker2d environment. As with Walker2d, the expert and imitator here are both stationary policies.
Car. We introduce a simple top-down navigation task where the agent is a "car" that always moves forward by one step, but can take actions to move left, right, or remain in its lane to avoid obstacles and reach the desired destination. There are M possible lanes. At timestep h E H + 1). if the agent is in lane E [M]. then the agent's state is (i, h). We view the state space
M x (H 1) grid; given point (i.j) in the grid can be empty, or contain an obstacle, or contain the agent. The agent's action space consists of 3 possible actions: stay in the current lane ((i, h)) + (i, h + 1)), move one step left ((i, h) + (i 1, / + 1)), or move one step right (ii, h) + (i + 1, h + 1)). If the agent's action causes it to collide with an obstacle or the boundary of the grid, is sent to an absorbing state. The agent gets a reward of for reaching the goal state for the first time, and a reward of O otherwise. When the agent occupies a state (i, h), observes an image-based observation 24 showing the state of all lanes for V steps ahead where V is the size of the viewing field. At the start of each episode, we randomly sample obstacles positions, the start position, and the goal position. The goal can be reached after H actions, and it is always possible to reach the goal.
Dyck. In addition to the RL environments above, we evaluate osgLo for autoregressive lan- guage generation with transformers (cf. Appendix B.3), where the goal of the "agent" to complete valid word of a given length in a Dyck language; this has emerged as popular sandbox for
22

---

Car (Log Loss)
Car (MSE Loss)
0.30
hortzon 10
0.30
hottzon 10
horizon 20
horizn 20
0.25
Expected Regret
horinos
Expected Regret
hostmon
0.00
0:15
0.15
0.10
0.05
0.05
0.00
5000
10000
15000
20000
5000
10000
15000
20000
Namber of Trajectoriss
Number of Trajectorics
(a)
(b)
Figure 4: Dependence of expected regret on the number of expert trajectories for Car environment under varying values for horizon H for log-loss (a) and mean- mean-squared loss (b). The expert policy network is trained on a set of 2 x 10 episodes generated by an optimal policy via behavior cloning.
We use LogLossBC to train imitator policy for varying values of the horizon H and number of trajectories n. For both losses, we find that the expected regret goes down as the number of expert trajectories increases, but degrades slightly as function of H.
understanding the nuances of autoregressive text generation in theory [100, 39, 12] and empirically [58, 95]. We recall that Dyck language Dyck, consists of 2k matched symbols thought of as open and closed parentheses, with concatenations being valid words if the parentheses are closed in the correct order. For example, if we define the space of characters as 'O', '[I', and 'I,, then '(OD() is a valid word, whereas '(DI" and "(((1) are not.
Our experiments use the Dyck language Dyck3- For our expert, we train an instance of GPT-2 small [64] with layers, heads, and 96 hidden dimensions from scratch to produce valid Dyck words. In particular, the training dataset consists of random Dyck prefixes that require exactly H actions (symbols) to complete. To imitate this expert, we train a GPT-2 small model with the same architecture, but with randomly initialized weights the expert. We assign a reward to each trajectory if the generated word valid, and assign reward 0 otherwise. We use Adam optimization for training, with our experts trained for 40K iterations in order to ensure their quality. Note that in this environment, the expert and imitator policies are non-stationary, but parameter sharing via the transformer architecture.
offline dataset of sequences generated by
C.2 Results
We summarize our main findings below.
Effect of horizon on regret. Figures and plot the relationship between expected regret and the number of expert trajectories for the Walker2d (MuJoCo), and BeamriderNoFramessip (Atari) environments, as the horizon H is varied from 50 to 500. For both environments, we find regret is largely independent of the horizon, consistent with our theoretical results. In fact, in the case of PearmederNoFrameskiip. we find that increasing the horizon leads to better regret. To understand this, note that our theory provides horizon-agnosti upper bounds independent of the environment. Our lower bounds are constructed for specific worst-case environments, and not rule out the possibility of improved performance with longer horizons environments with favorable structure. We conjecture that this phenomenon is related to the fact that longer horizons yield fundamentally more data, as the total number of state-action pairs in the expert dataset is equal to nHH. 13
Figure 3(a) plots our findings for the Dyck environment. Here, we see that with the number of theory first
trajectories fixed, regret does increase with H, which might appear to contradict glance. However, we note that the policy class itself must become larger as H increases, as the task itself becomes more difficult (equivalently, the supervised learning error D (PT" .P*)) must grow with H)). As a result, the regret is not expected to be independent of H for this environment, in spit of parameter sharing. To verify whether supervised learning error is indeed the cause for horizon
13 For example, if we repeat a fixed contextual bandit instance H times across the horizon and train a stationary policy, it is clear that regret should decrease with H under sparse rewards. Less trivial instances where increasing horizon provably leads to better performance are known in some special cases [87].
23

---

Log
MSE Loss
0.10
0.10
0.05
Expected Roget
0.05
horizon
100
horizon 200
Expectos
0.00
horizon 400
horizon 500
0.10
200
400
Number of Trajectories
Number of Trajectories
Figure 5: Dependence of expected regret on the number of expert trajectories for continuous control environment Walker2d-v4 under varying choices for horizon H. (Left) Behavior cloning with logarithmic loss (LogLossBC); (Right) Behavior cloning with mean squared error (MSE) Loss. Both losses lead to similar performance for this environment, possibly due to Gaussian policy parameterization.
dependence for Dyck, Figure 3(b) plots the logarithm of the product of the Frobenius norms of the weight matrices the expert for varying values of H. as a proxy for supervised learning performance [8, 37]."4 We find that the log- nromm do in fact grow with H, consistent with the fact that the regret grows with in this case.
For the Car environment, we observe similar behavior to the Dyck environment, visualized in Figure 4. We find that performance degrades slightly function of the horizon H, but that this increase in regret can be explained by an increase in the log-product-norm (Figure 3())). However, the effect mild compared Dyck.
Comparison between log loss and square loss. As ablation, Figures 4 and 5 compare LogLossBC to the original behavior cloning objective of Pomerleau [63], which uses the mean squared error (MSE) to regress expert actions to observations in the offline dataset. Focusing on the Walker2d environment (Figure 5) and Car environment (Figure 4) (other environments presented difficulties in training 5), we find that performance with the MSE loss is comparable that of the log- arithmic loss. For Walker2d, possible explanation that under the Gaussian policy parameterization use, the MSE loss is the same the logarithmic loss up to state-dependent heteroskedasticity. Another possible explanation is that this is an instance of the phenomenon described in ??.
Relationship between regret and Hellinger distance to expert. Finally, we directly evaluate the quality of (i) Hellinger distance D (P" .I²). and (ii) validation loss as proxies for rollout performance. We estimate the Hellinger distance using sample trajectories. Figure 6 displays findings for Walker2d with = n 500, where we observe that both metrics, particularly the Hellinger distance,
well correlated with rollout performance, measured by average reward. In Figure 6a, we see that under LogLossBC, Hellinger distance and validation loss are highly correlated with each other, and negatively correlated with expected reward, thereby acting excellent proxies for rollout performance. Meanwhile, in Figure 6b, we find that under behavior cloning with the MSE loss, validation error is less well correlated with the expected reward of the imitator policy, evinced by the cluster in the upper left corner, where there are policies with roughly the same validation loss, but variable expected reward. On the other hand, the Hellinger distance D3 still appears to predict the performance of the policy well, as is consistent with our theoretical results.
"We only include log- pog-product-nonee plots for Dyck and Car because for the other environments (Walker2d and BeammiderNoFrameesko we do not change the expert function of IT.
IIn particular, we attempted a similar result in the Atari environment, using MSE loss being between vectors on the probability simplex over LA actions. For MSE loss, we found that the imitator did not train, in the sense that even with 500 expert trajectories, the performance of the cloner did not improve. We suspect this due numerical instability in optimization for the MSE loss this setup or failure thyeerparameter optimization.
"In theory, the MSE loss can still underperforn the logarithmic loss when the heteroskedasticity is severe [32]. but this may manifest for this environment.
24

---

MuJoCo (Log Loss)
MuJoCo (MSE Loss)
Expected Roward
Expected Reword
1400
1200
1000
800
0.03
Di to Expert
Validation Loss
D2 Expert
Validation Loss
(b)
Figure 6: Evaluation of the quality of (i) Hellinger distance D [P B and (ii) validation loss as a proxy for rollout reward. We plot Hellinger distance and validation loss against mean reward for
single training run for Walker2d environment with H 500 and n 500. (a) Results for LogLossBC, where the validation loss and Hellinger distance D are highly correlated, and serve good proxies for the expected reward of the policy. (b) Results for MSE loss, where the validation loss is less well correlated with the expected reward (note the cluster in the upper left hand corner), but the Hellinger distance DA remains good proxy.
D Technical Tools
D.1 Tail Bounds
Lemma D.1 (e.g.. Foster et al. [34]). For any sequence of real-valued random variables (Xi)SST adapted to a filiration (F. ())SST, holds that with probability least 1 - ö, for all T" S T,
T
T
Σ
log (E S
Σ X, + 1))
Lemma D.2 (Time-uniform Freedman-typp inequality). Let (Xt)tST be real-valued martingale difference sequence adapted to filtration (Fr)ST. If [Xal S R almost surely, then for any n E (0, 1/R), with probability least 6, for all T T.
T
T
+ log(5-1)
Σ 1=1
X1
S n
Σ
E, E1-1
7
Proof of Lemma D.2. Let S. = Et X, and 1/2 = Σ.= E. X Let 2, = exp(1s: - V2).
As shown in Beygelzimer et al. [11] (see proof of Theorem 1), as long as 17 S 1/R,
E2 R (exp(xx(()X))) S exp(1) R, x
and so
E,- [Z] = E,_ (exp R, [x]]] 7--1 S Z- follows that (Zx) is non-negative supermartingale. Hence, by Ville's inequality, for any n (0, 1/R), we have that for any t > 0,
P St - v/V, 2 r] = P( 2, 2 e* se E "e We conclude by setting r = log 1og(8-1)/1) 1)/-
The following result a standard consequence of Lemma D.2.
Lemma D.3. Let (Xt)SST be a sequence of random variables adapted to a filtration (Fi) If
0 X. R almost surely, then with probability at least 1 for all T' < T.
T"'
Σ
X,
3
E [X,] + 4R 4 log(22-1)
2
and
T'
E
[X,]
2
X, + 8Rlog(28-1)
25

---

D.2 Information Theory
For pair probability measures and Q, we define the total variation distance as Drv (P, =fIP dQ), and define the X²-divergence by (IP ?
(dG=
if IP < Q and
du
(P Q) +o0 otherwise. We define KI. divergence by DKL (TP QQ) = J dlp log P < Q and (PL(P)) too otherwise.
dB if
de)
The following lemma states some basic inequalities between divergences.
Lemma D.4 (e.g., [62]). The following inequalities hold:
(P, Q v (P, Q) - 2Dvv(P,Q). Q)
[D Q) E Dx² (P (1P & Q)..QQ.
D.3
Reinforcement Learning
The following lemma a somewhat standard result; see, e.g., Lemma 15 in Zanette and Brunskill [101]. We include a proof for completeness.
Lemma D.5 (Law of total variance). For any (potentially stochastic) policy n, have
H
Var
Th
= E
Var [rh + Viti(#N41) In
L
with the convention that Tu is deterministic dummy state (so that Po(æ1 = 20, a = is the
initial state distribution) and ro O.
Proof of Lemma D.5. Let h E {O...., H3 be fixed. We can expand
Var
Σ
DT
Σ
Vn (EWN)
ah
F-h
11
V (0+1(1 + (rn + V (x V%5 (zw)))
E"
25
k=1+1
H
1T
Σ re- - Vi
Vitta (ita(
on + + Irr( + (h+ta - V/ (xnn)) 2x
M==++
"1
+ 2
Σ Vita(anti))
(rn Vitz(an4)) V/5 (x())) Imn
(=1+1
E
re - V Vitt (on+1)
xn + +B*[(rn + ( - (x [M)]
H
E
V +
Σ
re Th+1
| 1
+ Var [(ra + Viti(aN4 [n].
1=++1
We conclude inductively that for all h E {O....,,H! H).
Var
re
Wh Σ
Rd
[Var* [(re
V ( we] [nn]
t=h
To obtain the final expression, note that
H
H
V
Σm
Σ
Th
= V
Σ
Lh=0
under the convention that Zn is a deterministic dummy state (so that Pi Pi = Io, state distribution) and ro 0.
I a) is the initial
26

---

D.4 Maximum Likelihood Estimation
This section presents a self-contained analysis of the maximum likelihood estimator (MLE) for density estimation. The results are somewhat standard (e.g., Wong and Shen [97], van de Geer [89], Zhang [102]), but we include proofs for completeness.
Consider setting where we receive {=') )=);=1 i.i.d. from ~ where O" E (2). We have class
C (2) that may or may not contain g² We analyze the following maximum likelihood estimator:
= arg max
Σ log(s(="))-
(10)
gEg
1=1
To provide sample complexity guarantees that support infinite classes, appeal to the following notion of covering number (e.g., Wong and Shen (97]), which tailored to the log-loss.
Definition D.1 (Covering number). For class G C A(Z), set that class G' C (ZZ) is an E-cover if for all g E G, there exists g' E G' such that for all z E Z, log(g())/d S.. e. We denote the size of the smallest such cover by Nog
We also allow for optimization errors, and concretely assume that 9 satisfies
Σ log(O(=")) 2
Σ log(g(>')) - Eopt
max gEg
for parameter Copt 2 0; the case Eopt 0 coincides with Eq. (10). Our main guarantee for MLE is as follows.
Proposition D.1. The maximum likelihood estimator in Eq. (10) has that with probability at least
1 1-8,
D=(O.g") S inf (log(2Ming(G,e)/6- + 48 + inf log(1 + Dx=(g" 9) + 28 E>0
gEg
In particular, if G is finite, the maximum likelihood estimator satisfies
D²( - 6log(2(g)/8-)) + inf log(1 + Dy² (g" g)) + 2E
gEG
Note that the term inf geg log(1 + (g* g)) corresponds to misspecification error, and is zero if g" g.
Proof of Proposition D.1. Let Ge denote a minimal E-cover for 9, and let g E Ge denote any element that covers ÿ in the sense of Definition D.1. Going forward, we will that ğ satisfies
Da 9) 1 DK 11 S.
(11)
Let (g)) = - log(g(2)), and set I(g) = - log(g(z')). Set Xi(g) = - applying Lemma D.I with the sequence (Xx(g)) for each & E Ge and taking a union bound, have that with probability at least 1 - 8, for all Ge
By
-n- log (Bagg [ed (18t0
(f(g) - -i(00)) + 1og(() 2
Using a standard argument [102], we have that
- log EEswg' [et loxlots)/o" (+))) log
1 1 )Di(o.0') 2 ph(o.9").
1
In particular, this implies that
Dā(ā.g") 2log(191/0-1) (i( D(g"))
n
n
and so
4log(191/511) 2 (i -i('') + 25,
Di(0.gg) < 2D)() 2D.
27

---

by the triangle inequality for Hellinger distance and Eq. (11).
It remains bound the right-hand-side. Let 9 be arbitrary. We can bound
( F(gg' < T T.( + T.(g) [(gg)) s T.() T() + T(gg) T.(gg) + Copt (12) by the definition of the maximum likelihood estimator. For the first term in Eq. (12), observe that
i@ - -(g") = log(g (z')/((2)) & en,
by Definition D.I.
To bound the second term in Eq. (12), set Y; ((b(gg) - Er (g))). Applying Lemma D.1 with the sequence (Yi)==>> have that with probability at least 8,
L - I(g") S n log (Eangr [c (clxx(0((3//(66)) (=1/3(=))]
log(6
Finally, note that
log (Bengr [clorla (83/5(=))) [ = log Exzg'
g g'(2)
log(1 2x² g])
[(=)
The result follows by choosing ÿ minimize this quantity.
Part I
Proofs and Supporting Results
E
Examples and Supporting Results from Section 2 and Section 3
This section contains supporting results from Sections 2 and 3:
Appendix E.1 presents general sample complexity guarantees for log-loss behavior cloning that support infinite policy classes and misspecification, as well as concrete examples.
Appendix E.2 formally introduces the online imitation learning framework, and gives sample complexity guarantees for a log-loss variant of Dagger.
E.1 General Guarantees and Examples for Log-Loss Behavior Cloning
In this section, we give bounds on the generalization error D2 (P", for log-loss behavior cloning for concrete classes II of interest. To do so, we observe that the log-loss behavior cloning objective
arg max
log( (aj xf)))
#Ell
Y=1 A=1
is equivalent performing maximum likelihood estimation the density class P (PM) xell Indeed, for any æ E II, we have
H II h=1
Σ log (TT(((() (o') = 1=1
Σ log
Po(+f)
Pa Pa The ahh)
1=1
H
log(Ta(aj, xx))) + C(D),
where C(D) is constant that depends the dataset D but not It follows that both objectives have the same maximizer. Consequently, we can prove sample complexity bounds for log-loss behavior cloning by specializing sample complexity bounds for MILE given in Appendix D.4.
To give guarantees that support infinite policy classes, we appeal to the following notion of covering number.
28

---

Definition E.1 (Policy covering number). For class II C fmh: &' + A(A)), we set that IT' C {Th : X ](A)) an e-cover if for all π II, there exists II' such that for all E X, a E A, and h E [H), log(ma(a x)/=/ (a x)) S e. We denote the size of the smallest such cover by (Pp e).
In addition, to allow for optimization errors, we replace Eq. (4) with the assumption that म satisfies
H ( (oh. (1))
H log(TTA (aj. (hh)) Copt.
max mET
(13)
for a parameter Copt O: Eq. (4) is the special case in which Capt = 0. With these definitions,
specializing Proposition D.1 leads the following result.
Theorem E.1 (Generalization bound for LogLossBC). The LogLossBC policy in Eq. (13) has that with probability at least ó,
6 6 pol (II, EIL, + 48 + inf log
DR
pa
1000
inf E20
1 Dx2 (I 21P" || 11))) + 2oopt.
71
Tell
In particular, if is finite, the log-loss behavior cloning policy satisfies
6 61og(2(1100-)
D Pd ( (P.,p""))
n + inf log 1 + Dya (P="
(Pt) 28apt.
REll
Let us make two remarks.
First, the only explicit dependence on the horizon is through the precision E/H through which we evaluate the covering number: (I,, As result, for parametric classes where NNoo (II, e) x log(s-²) (we will give examples in the sequel), the result will scale at most logarithmically in H, but for nonparametric classes the dependence can be polynomial.
Second, the remainder term inf en log(1 + Dx² (IPT" || [T)) corresponds to misspecification error, and is zero if 'T E II. We remark that when n is deterministic, this expression can be simplified to en log E
IH [x(an[za]]
Proof of Theorem E.1. This follows by applying Proposition D.1 with the class {PT), ren and noting that if n' covers in the sense of Definition E.I, then for all E (X A) have log(P"" (o)(P"))) (o)/P=((o) & eH, meaning that an E-cover in the sense of Definition E. yields an eH-cover in the sense of Definition D.1.
F.1.1 Example: Tabular Policies
We now instantiate Theorem E. to give generalization bounds for specific policy classes of interest.
Consider tabular MDP in which |x8', |A| < of all stationary policies leads to a bound independent of H.
small and finite. Here, choosing II to be the set
Corollary E.1 (Stationary tabular policies). When IT is the set of all deterministic staiemmo policies, the log-loss behavior cloning policy Eq. (4) has that with probability least 8,
(
( [og]|o
DR (TP_,PT)) So
72
Meanwhile, II the set of all stochastic stationary policies, the log-loss behavior cloning policy Eq. (4) has that with probability at least 1 55
(P p=" < zŌ (1x|IA ((((21144) [ollA)oo((F))) (Hn5-1n
Proof of Corollary E.I. This follows by noting that we have log[U]] < | log|A4 in the deterministic case and Log.Npoll (11, (((*')))) log(s-1)) in the stochastic case (this follows
29

---

from a standard discretization argument, e.g., Wainwright [91]).
Naturally, we can also give generalization guarantees for non-stationary tabular policies, though the sample complexity will scale with H in this case.
Corollary E.2 (Non-stationary tabular policies). When 11 is the set of all deterministic non-stationary
policies, the log-loss behavior cloning policy Eq. (4) has that with probability at least 1 ô,
(F s H
log([AA8-1)
n
Meanwhile, I1 is the set of all stochastic non-stationary policies, the log-loss behavior cloning policy Eq. (4) has that with probability at least 1 6,
( 1rT) Ō || log(Hno
Proof of Corollary E.2. This follows because we have log II| S H| |o in the deterministic case and log poo (1L, s ÖH logA in the stochastic case.
E.1.2 Example: Softmax Policies
Next, we give an example of general family of policy classes based on function approximation for which the sample complexity is at most polylogarithmic in H.
For vector R.A, let
(AA) be the softmax function, which is given by R-
exp(v.)
oa(v)
Exee exp(ue)
Let F C X be a class of value functions, and define the induced class of softmax policies via
II, = =
where
= (= (f(u
We give sample complexity guarantees based on covering numbers for the value function class
Definition E.2 (Value function covering number). For a class F C {fn X' A- R}, we set that F' C {fn X A + R} is an c-cover if for all f E F, there exists f E F' such that for all X, a E A. and E [H], [s((,, a) - (1, a)l S e. We denote the size of the smallest such cover by Neal (T),
Corollary E.3 (Softmax policies). When = IT is the softmax policy class for a value function class F, the log-loss behavior cloning policy Eq. (4) has that with probability at least 1 8.
Di p
p=
0(1) inf e>0
+e
inf log 1 (1+Dx=(P**) (PT)
Proof of Corollary E.3. Consider pair of functions f, with Ifn a) (z) S for all I E X. a E A, and h E [H]. The induced softmax policies satisfy
Σ Ever exp(((tt)))
log(TT
x)) = fa( (x, + log
Exed
Clearly we have (n f1 (1, a) S E, and we can bound
log En'es exp(Ji
Cocresex([Jaee (x,)))) a')) (xp() In (M(o)))))))))))
log
Eaed exp(fn(z,a1))
EoEA exp((f((xxa)
Enres exp(F maxa exp(f) - (x(x)a)))
log
ExeAexp(Ja(an
(fh(l, - fn " Se. a"
max
30

---

Hence, e-cover in the sense of Definition E.2 implies a 25-cover in the sense of Definition E.1.
Whenever F parametric in the sense that Mmg & log(e-"), Corollary E.3 leads to polylogarithmic dependence H. The following result gives such example.
Linear softmax policies. Consider the set of stationary linear softmax policies induced by the value function class
F= f=x h) (on(x, 0) 1001 - B),
where on (z. a) E IR' is a known feature map with (l aa) - B. Here, we have log ( E) x dloo( BE 1) (e.g., Wainwright [91]), which yields the following generalization guarantee.
Corollary E.4. When II is the set of stationary linear softmax policies and x² E II, the log-loss behavior cloning policy Eq. (4) has that with probability least 1 -
(T PT'' 0 (dlog(BHnod1))
E.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger
In this section, we give sample complexity bounds for a variant of the Dagger algorithm for online IL [72] that uses the logarithmic loss. The main purpose of including this result to give end-to-end sample complexity guarantees for general policy classes, which we use in Sections 2 and 3 to compare the optimal rates for online and offline II. For this comparison, we are be mainly interested in the case of deterministic expert policies, but analysis supports stochastic policies, which may be of independent interest.
Online imitation learning framework. In the online imitation learning framework. learning proceeds in n episodes which the learner can directly interact with the underlying MDP M and query the expert advice. Concretely, for each episode
[n], the learner executes policy o = {TH X + ((A) and receives a trajectory of = (xi ai " (1' ang a"y') ), in which aj Ti. (xrt)). a ~ x (xf)), and ri+t1 ~ Pa (1r,, at)); in other words, trajectory induced by the learner's policy annotated by the expert's action aj z (2%) at each state iy encountered. After all n episodes conclude, they can use all of the data collected to produce policy स such that J(x*) ( is small.
Dagger algorithm. We consider general version of the Dagger algorithm. The algorithm is parameterized by an online learning algorithm Algest which attempts to estimate the expert policy in sequential fashion based on trajectories.
Set D Ø. For 1,..., n.
Query online learning algorithm Algest with D' and receive policy f.
Execute a and observe of = (z) ai","""),,........ (F'r ain aii')
Update D + (o')
At the end, we output मे = unif(T') (T',..,,,*)) as the final policy.
To measure the performance of the estimation oracle, we define the online estimation error as:
H
Est on (n) = ΣΣ R (
As we will show in moment, this notion of estimation error well-suited for online learning algorithms that estimate n² using the logarithmic loss.
Our following result gives general guarantee for Dagger that holds for any choice of online learning algorithm. To state the result, let |p="|> |- denote the law of o (I1, ...,... (æ aH, azz) when xt is the expert policy and we exccute म. Let
T [QT (æn, and - V (xx))²
x
31

---

so that o.t = = and define T.. = sup, of Note that o.. = 0 whenever T is deterministic, but general, o.. 2 o
Proposition E.1 (Regret for Dagger). For any MDP M with signed recoverability parameter ja and any online learning algorithm Algest Dagger ensures that
-(T') S 0 Est (n) + EstH (n).
Furthermore, whenever It is deterministic,, Dagger ensures that
- ((F) S Est.
(14)
To instantiate the bound above, we choose AlgEst by applying the exponential weights algorithm
(e.g., Resa-Bianchi and Lugosi [19]) with the logarithmic loss. Let 1I, == {Th E II} denote the projection of II onto step h. The algorithm proceeds as follows, At step i E [n]] given the dataset D'
for each layer h [H] we define a distribution pij E A(II;) via
(T) x exp
Σ log( (a (
II JC
Th (h #0 (x)))
We then
i 2) = E Eanun [Tn (a x)].
We refer to the resulting algorithm as ossDagge..... This leads to the following guarantee for finite classes.
Proposition E.2 (Regret for LogLossDagger). When x² II, the log-loss exponential weights 8,
algorithm ensures that with probability at least
2 Σ l0)((11(18-1)).
Est on (n)
n2
Consequently, LogLossDagger ensures that with probability at least 1 - 8.
H
log([Inn|HH
log( (H6
22
+ F4
12
h=1
and when n² is deterministic,
log( [ (H811
- S
We note that for many parameter regimes, the sample complexity bound in Proposition E. can be worse than that of LogLossBC in Theorem 3.1 (for stationary policies, Proposition E.1 has spurious dependence on H. and the variance-lii like quantity in the leading order term is weaker). would be interesting to get the best of both worlds, though this may require changing the algorithm.
Proof of Proposition E.1. Consider an arbitrary policy म. Begin by writing
H
J(x') - (
Σ
R
QT (Rh, (k(()) Q (Rh, an)]
h=1
Fix layer h. By Lemma 3.1, we have E
QQ (an, mb (mr)) - QR ax))
ET QT (ox, (x()) Q (In, an)
+ (1 [QO"" (Ia. n. (Ir)) - Q (uN, an))a] - ((OT" (#n, (xn)) - Q (In,)a))²]) E (FTa (x(x))
(B* (B"""((Q) (mh, n (xn)) 0% (x), an)) A [Q (*h, o (xx)) Q (xn, an ()))) E [D3 (M (wx), क (xx)))
32

---

Furthermore, using Lemma 3.1, we have
E
(QR (Th oे (x+)) Q% (In, an))
H
H
(Q (oh, mx - Q% (on, ax)) E
+ 1:-0 E =f
so that
E
||
Q (oh, n (xN)) Q% (xt, and
(15)
E [Q (oh, m (FA) - 0% (Nes a+))))
(x + + E. (T o (xn)))
Recall that the Dagger policy satisfies
n Σ
-
-
i=1
Applying Eq. (15) to each policy #', summing over all layer h, and applying Cauchy-Schwarz, yields
n
J(T*) ((F) z
0² lad
Est. (n) + + Est (n)
52. Est. + Est. (n).
In the deterministic case, we tighten the argument above by applying the following improved change- of-measure argument based on Lemma 3.1:
ET
1 QR (Ins ((n,mT(())) (xn)) Q% (rn, an)
< -
[Q (In, (/ - Q% (In, ax))+
I 2 E
(QT (2n, QR (cn,,))) + p E (xN)
= E (TN)
This leads Eq. (14).
Proof of Proposition F.2. Since n² II, standard guarantee for exponential weights with the log-loss (e.g., Cesa-Bianchi and Lugosi [19]) ensures that for all h E [H]. the following bound holds almost surely:
Σ log(1/R((a))
(x)))) S
log(1/7h(a))
|
log [.).
From here, for each h E [H] Lemma A.14 of Foster et al. [34] implies that with probability at least 8,
x
(x)) s log| 2log(6 ) E
The result now follows by taking a union bound.
33

---

Proofs from Section 2
F.1 Proof of Theorem 2.1
Proof of Theorem 2.1. We begin by defining the following trajectory-wise semi-metric between policies. For a pair of potentially stochastic policies π and T. define
p x²) = EE" B ~ (L on + d/)l
where the shorthand d It' (#1.8) to indicate that a' T/ (z1), ................................ a& IH (x Despite being defined in an asymmetric fashion, the following lemma shows that the trajectory- distance p(: -) is symmetric, from which it follows that it is indeed semi-metric.
Lemma F.1. For all (potentially stochastic) policies a and x', it holds that
p( ll n²) = p(xx x).
Next, we show that it is possible bound the difference in reward for any pair of policies in terms of the trajectory-wise distance p(: -).
Lemma F.2. For all (potentially stochastic) policies a and x', it holds that
- R. p(T x²).
Finally, using Lemma F.I, we show that when one of the policies is deterministic, the trajectory-wise distance is equivalent to Hellinger distance up to an absolute constant.
Lemma F.3. Let IT" be a deterministic policy and n be an arbitrary stochastic policy. Then we have that
4 p(
x]x S DH IT,
2. p(= T).
Combining Lemmas F.2 and F.3, we conclude that for any deterministic policy x' and stochastic policy म,
- - < 4R (P Pm')
Proof of Lemma F.1. This follows by noting that write
p(T || T²) = - ET Bel (2xa))) a/, Vh]]
H
Σ
Po(x1) II
Px
Dhs (a) In))/((h mn)[{aan = a'
H
Σ
Po(as)
II h=1
Ph Pa
Th Tn I In)ll(an = a//}
E Eag
( ah, vh]] p(a' m)
Proof of Lemma F.2. Observe that since Σ# Th E [0, RJ. we can bound the reward for
J(T) < -
Σ Th
= an VhH]
R. E
af + anl
H
= TT
(an = whH]]
+ R p( x').
A=1
34

---

We can bound the first term as
E
Σ Th
foi an thi]]
E" f(ri. a1d Be = on wh3]]
where ((HHH = D Birn Ihe anl. We now observe that for any function f.
E" [( (1:H) - [L on WhH]]
E
(ai.H Po(æ1) II h=1
Pa In (h (n In In) wm)]{aan = =a/}
#1.8 1ii
Σ
I(LHH dIH)) Po(x1) h=1
II
Pa oh. mN) xn)T(an = =0/}
Ff II
f(ZLH, Po(x1)
Pa (1 Ih, "hn.h)m mp))
h=1
=E [f a1.H)).
We conclude that
E"
Σ h=11
th
Bai (oinn an whill {((T),
so that
s R p(t (1).
Proof of Lemma F.3. Define the triangular discrimination via DA [P. Q = (dP- 42)2
dF+ and recall
that D Q) < (P,, Q) < (P, Q) (e.g., Foster and Krishnamurthy [32]). Next, define the shorthand P(11. 01-H)
T P( Th, ax) and Pa (01:H f1:H) == I Th (a, mx) (these quantities do not have an interpretation as conditional probability measures in the way the notation might suggest, but this will not be relevant the proof). For any deterministic policy n², we can write
DA (I=,,=**)
(a F1:H) p=
(a1.1 11:H))²
ΣΣ
P(ZnH (1-H1))
(= [1:H) + pr' (a1.H F1:H)
F1.8 01:
(P*(a1.t) T1:H) p
(a1:H (1.H))²
Σ
Σ
P(ZLH (1.H-1)
(* (1:H)) px
(01.1 (1.HH)
Zii 01:
(PT (a1. #1.H) pm (a1. [1:H))²
P( (1.H1))
Pa (a
(1:H) + Pm (01:1 F1:H)
FLB AL
Since T² is deterministic, p= (a1. 71:H) if a1 = T" (x1.1) and pa" (a1:H (1:H) otherwise. Using this, we can write the second term above as
(P (a P* (a1.1 (1:H) 0
[1:H) - 0)2
Σ E
P (LH-1)
#1:
t (ZLH)
Σ
Σ
P (1:H-1) (a1.H [1.H)
Eh: + n (xx)) = p( T*)
35

---

This proves that Da (I",,""") 2 p( || T²). For the upper bound, we use that IT" is deterministic once more to write the first term above as
(P (a [1.Hr - 1)
Σ
E
P(ZL: (1.H-1)
(= 21:H) +
a1d =n (21.)
(PT (a1:
[1:H) - 1))
E=
E" [(P" (a1:1 [I.HH - 1)21.
pa (a1:H [1:H) +1
We further note that
ET (PT (01.H H [1iHH) 1)
EET
[1 + (PM (d':1 [1:H) - 2)1{a = a1.8
S E² Eat [1 I[a = d1:H1 H
ET Eag [T(3h: ah. # an.H)) p( T).
By Lemma F.I, we conclude that DA "Pp,,"") ) S p( |l π*) + p(** || xx) = 2p(m || T).
F22
Proof of Theorem 2.2
Proof of Theorem 2.2. For this proof, we consider a slightly more general online imi- tation learning model in which the learner is allowed select aj based on the sequence (z), af
(2) 1 "h-1)) (2%, aa")) training time; this subsumes the offline imita- tion learning model. Let E N and H E N be fixed. Let A (0,1/3) be a parameter whose value will be chosen later.
We first specify the dynamics for the reward-free MDP M and the policy class II. Set X' = (x. y} and = {a. b). The initial state distribution sets Po(x) 1 A and Po(y) = A. The transition a) If2x = x for all h; that is, x, y are self-looping terminal states. We set (T", n' J. where the expert policies are n", which sets म (2) = a for all h and x, and x", which sets oi, (x) = a and sets Ti (y) b.
dynamics are Pa. (x'
Let problem instance I (M* . x*) refer tuple consisting of the reward-free MDP M*, a reward function r {rr] and an expert policy x². We consider two problem instances, I = (M*,r", r") and I = (M* r":","";"") x"):
For problem instance I', the expert policy is n². We set rj (x, -) 0, rj (u. a) Ifa a} for all h.
For problem instance P, the expert policy is n'. We set r (xx 0, r (u, T(a b} for all
Note that both of these instances satisfy = 1, and that x² and n² are optimal policies for their respective instances. Let J denote the expected reward function for instance Z", and likewise for Z".
Going forward, we fix the online imitation learning algorithm under consideration and let IP' denote the law of o² ......"" o when we execute the algorithm on instance a, and likewise for b; let EE||-] and E. denote the corresponding expectations. In addition, for any policy π. let |=*l> denote the law of (x1, .1, ai),.... (HH, (H, (zz) when we execute in the online imitation learning framework and the expert policy is n² '', and define Ipr") analogously.
We first observe that for any policy R.
- = =A
Σ
E on (g) Uan # (y))},
and that J(r) A Σ# (y # T (y))). Defining p(x,T') ElL N3 (g) I(an # a/}} as metric, we note that p(T', = H, and hence by the standard Le Cam two-point argument (e.g.. Wainwright [91]), the algorithm must have
AH
max -())) J{A)
4 DIv(P',P))
36

---

where Drv(:,) denotes total variation distance. Next, using Lemma D.2 of Foster et al. [36], we can bound
DTv(P, P) SE
Σ Du p p
Since, the feedback the learner receives for a given episode is identical under instances and I unless 21 (regardless of how n is chosen), we can bound
D pp"ll" p |r'
S 2A,
and hence
(IP S 14An.
We set A 1/56n, and conclude that any algorithm must have
AH
H
max - (())))))((())) J())
8
71
for absolute constant 0.
G Proofs from Section 3
G.1 Proof Theorem 3.1
Proof of Theorem 3.1. Assume without loss of generality that R Let o (21, a.)...,... (HH, ag) ), and for each h E [H], define the sum of advantages up to step h via
h
An(o) = Σ QT (Ie, - Q7 (Iz, ae)):
E=1
which has [A()) H almost surely. Consider the filtration F (z a1...........................a.. The ah). Fix parameter L whose value will be chosen later, and define a random variable
H == min [A)( > 4}.
with 11* = if there is no h such that (o) L; we will adopt the convention that Qh+1 VØ++1 0.
Lemma G.1. H is a stopping time with respect (Fr) and has Ah- (o)) L + almost surely.
The following lemma, which is one of the central technical components of this proof, gives bound on regret in terms of the expected advantage at the stopping time H*, We use the stopping time to keep the sum of advantages Aи- bounded, which facilitates strong change-of-ne of-measure argument in the sequel.
Lemma G.2 (Regret decomposition for stopped advantages). Ifrk 2 0 and Σ Th E [0, RJ. then for all policies म. we have that
J
(
R 1 H < H). < E A (o)]
(16)
Note that even though we assume Rt = 1 throughout this proof, we state this lemma for general R for the sake of keeping it celf-contai
We proceed to bound the right-hand-side of Eq. (16) using change- -lange-of-measure measure based on Hellinger distance (Lemma 3.1). For the second term in Eq. (16), Lemma 3.1 gives
IH < H < 2PF=' H
< H + D2 P .p='"
2|==" 13h
A (0) LT + D
p por)..
17Tha is. for all h, 1(h H"} measurable function of (æ1, a1) ..... (on, an).
37

---

For the first term in Eq. (16), Lemma 3.1, gives that
E [ (o)] S ET [An- (o)] + E [t) + E [ (o)l) (ol)) DH (Pa p
To bound the first moment and second moment of A (o) under πT,, we use the following lemma, which follows from elementary properties of stopped martingale difference sequences.
Lemma G.3. We have that
E" An-(()) S 0, and E
A [o)] I 4o
remains to bound the second moment under म. Here, since | (o) S L + 1 almost surely by Lemma G.I, we note that Lemma 3.1 gives
p ) A (o) = 22 (0)) + (L+ (I+
Combining these developments, we have that
E A (o)] S V 2 E | (o)] D (IPR, par) + (L + D (P" [p",ppx"
v 60z (P pPr) + (L Di π pa
and thus
S V60 DH((F, + (L + 2) IP _aa (eR,
22 [3h: |An()) L}.
To wrap up, appeal to the second of our main technical lemmas, Lemma G.4.
Lemma G.4 (Concentration for advantages). Assume that rh 2 0 and Σ Th E [0, R) almost surely for some R >> 0. Then for any (potentially stochastic) policy n, it holds thatfor all 8 E (0,e-))
H'
p
3H's :
Σ
(T an) - V/ (2n) 2 cc.Rlog(8-1)
8
for absolute constant > O.
Let E e0,e be fixed. we define
L c- log(E
where >> is sufficiently large absolute constant, then by Lemma G.4, we have that
p [h: [)](o)) > L] s.
This proves the result.
Proof of Lemma G.1. To prove that H* is stopping time, we observe that for all h S H, we have I(h H³} T(|A. (o)) A, (0) S L 4h < <h), and (o) is a measurable function of (z), a .... (Ix, a,). Likewise, we have I(h H* 1) (o) vh H), which is measurable function of (æ1, a1), (IH, ax). For the second claim, observe that
A (o) S [A)) + Q (œ mi. (an-)) Qh (xn-,
< L++
almost surely.
38

---

Proof of Lemma G.3.
Define X == 0% (In, (x)) (h an), and Fb
(a1 (l1.---. 0n)) with X O. Since H' is stopping time with respect to (F)) and XA is a martingale difference sequence (under ग T)), the optional stopping theorem (e.g., [96]) implies th
H
1E
E
Σ
X
=0
We now bound the second moment. Recall Doob's 's maximal inequality (e.g., Williams [96]).
Lemma G.5. If (SA) is non-negative submartingale, then
E
S
|
KE(H]
We claim that [o) is submartingale, since a convex function of a martingale is submartingale. 19 As result, Lemma G.5 gives that
E B[A (o)] S E
max A mE
< <4E[A
Finally, we note that
H
E" [A)[(o]
= E=*
Qh (an, (((x) - Q% (2hr an))
1=
H
1x
[10T (Ins mx(x)) Q7 (In, an)) =o
h=1
where have once more used that Xs. Q (on, (mn, (xx)) QR (In, an) is martingale difference sequence.
G.1.1 Proof of Lemma G.2 (Regret Decomposition for Stopped Advantages) Proof of Lemma G.2. Consider the following non- Mon-Markovian policy:
h H h H*
m (- 1i 01:h-11
Dh.
This is a well-defined policy, since we can write I(N' H*) is measurable function of (11,01),... (#w, aw) (x1, 01) a.)........ ...., (8h-1, a4-1) for h' < h.
I(h > H*} = max T(ll' = H*), and
We begin by writing
JTT)) J(f) J -
(17)
For the second pair of terms in Eq. (17), we use the following lemma.
Lemma G.6. Under the same assumptions Lemma G.2, it holds that ( - ( < R
Fa H < H).
To give self-containe, proof, note that we can write E=
Σ X = E" ΣN Xx1((t 2 h}
We claim that T( 2
is a measurable function of Fh-1, since T( h) = 1 1(H <h), and
H = h'F is measurable function (I1, 01)...., (MA(,0w) C (2i, (1,, (Ih-1, -1-) for
(0)),
We conclude that 8= [Xx.((H'' 2 h) [.-1] E Xx, 1r- A) =
'For completeness. note that [o)A Fnn] = B[AA-1(0) + + Fr-1] > [A-1(()) + E|Xn f.-1]] = An-1(o)).
39

---

For the first pair of terms in Eq. (17), using the performance difference lemma, we can write 20
Q7 (In, (xn)) - Qh (æn, an)
- 1x
En-1 QR (T - 28 (Ine ond]
1
En- Q% (mn, (xx)) Q% (In, mn) ( TT m7))
E
En-1 ( (Mn)))()))) Q (o an) I(h a1 H1]
E*
H
x
27 (on, (xn)) - 07 (Dn, an) =
where the third equality uses that (- 01h-) (- mn) for 11", and the fourth equality uses that 1 S H*} is Fn measurable.. We now appeal to the following lemma, proven in the sequel.
Lemma G.7. Under the same assumptions as Lemma G.2, it holds that
E E B*(AH-(O))
E 1²IAu-(0)) (o).
Altogether, conelude that
S AHH R- 1PT1H"
[H" S H).
Proof of Lemma G.6. Let us define f(o) = Σカ= E[rn that g(o) indeed measurable function of o (æ1, a (a),,.... (IH an), since I1 H}
Ih. an) and g(o) 1 I]: note
1 I < H), {H* < H} UnSH = h}. and (H* = h} is a measurable function of (x1, (1....)..... (Zh, an). We can write
H (Em
( S E*
HH > H} + R- < H].
(18)
Let us adopt the shorthand P( (aHH-) := H-1 Ph(x441 Ih, an). We can bound the first term Eq. (18) via
(n).
Σ Th -=1
1H
H}
= Σ P(o)a)) (1:H-1) II
7 (an T1:h: Q1:h-1)
h=1
Σ
((0)g())P(( (1:H-1) II 7 (an (p))
h=1
Σ
f(o) (1:H-1) II
# (an IT)
h=1
H
Fh = [()),
Since is non Non-Markovian, we need to expand the state space to x/j = Fish 01 to apply the performance difference lemma, but since n² itself is Markovian, this results in the claimed expression.
40

---

where the second equality uses that T(- 21sh. R1:4-1) = T(- (ah) for all h E [H] whenever g(o)
To bound the second term in Eq. (18), we can write
P H S
P H =t].
For each h, let on == (21, a1),........ (0), an) and gh (ox) I h} (recall that I h} measurable function of (I1, (1),...)............... (Ih, an)). Note that for each h, if we define P(
a1:h-1) = I Pe(xe+1 I2, ae), then
p IT1H"* h]
Σ
gh (n(n))((z1))) (i II me(ar
[=1
h
Σ
(,(on))(F1o.)
01:h-1) 1) II Re(ae) we)
Oh A
P [ h]. h).
where the second inequality uses that 7(- 01 (12-)) x2) whenever & & H
Proof of Lemma G.7. We start by writing
E A H- (o)]
h=1
For each h < +,1, let o == (x1, (1), ai)..... (2h. an) and (on) == I[H = -h} (recall that I(H* = h] is a measurable function of (2i.a))..... (Dp, az)). For each H 1, define P( (14-1)= = II Pa(xe+1 de, a;), then
h In (n(o (11-1) II
B" = [o), = E
#z(as Tie,
8=1
Σ
gh (ooo))anon)P((nn (11h-1) II Re((a xx)
A
T [TH M)An(o))
where the second inequality uses that 7(- (1ee, = #(- xz) whenever &. E H
G.1.2 Proof of Lemma G.4 (Concentration for Advantages)
Lemma G.4 is proven using arguments similar those in Zhang al. [104, 105], but requires non-trivial modifications to accommodate the fact that ı an arbitrary, potentially suboptimal policy.
Proof of Lemma G.4. Let abbreviate Q Q" and V = Va Assume without loss of generality that A 1, and note that this implies that rh E [0, 1] and Qn, Vn E [0, 1], which we will use throughout the proof.
(IV-1, Define filtration Fn-1 (((11, ((. (h--1, vn). Since
Fn-1(Qu(zz ax) (*x)] = 0.
two applications of Lemma D.2 and union bound imply that with probability at least 8, for all H' E [H]
H'
Qu(zn (i())) S
E [(QN(In) Vx(x)))) [x]] log(28
#=1
41

---

Since E" (Qn an) 2/l (zn,,,,, we can write
H1
E [(Qn an) Vi(ln))2 mn
E
[OA an) | (z))
h=1
H'
E [[0] (z), and [n]] ( + (0 12(x1))
H'
an) [xn] ((+t((1411) + E
1=1
Observe that by Jensen's 's inequality, we have E [QQ (Th, ax) mn
I E (rr + Vh+1 (14411) )) mm
= E" (1+1((1411) an
+ E" [r mal + 2E V++1((n+11 x
I E" Vhita (3n44))
+3 +3B*rr (rn xn),
so that
H'
E" [QQn an) (xx)))
S
Σ
E
h
(TT+1) snp]
+ > E [rn mn +
h=1
By Lemma D.3, we have that with probability least 1 8, for all H' [H].
H'
H'
[rn
nh log(28-1)
h=1
h=1
+ 1og(28-1).
Likewise, by Lemma D.2, we have that with probability at least 1 ö, for all H1' E [H],
ET V2+1(1144)) (x7441 mn] (1+4())41)
ET (V (2 E [ (2n+1) mxn)) xn + log(0-
W Var [V ( xn]] + +og(0=1
h=1
H' $ Var W xxl + log(5-1).
h=1
where the last line uses the following lemma, proven in the sequel.
Lemma G.8. If X is random variable with |X] S 1, then
Var( < 4Var(X).
We now appeal to the following lemma, also proven in the sequel.
Lemma G.9. Under the same setting as Lemma G.4, we have that for any 8 E (0, 1), with probability least 20, for all H' (H).
H'
Σ
Var (VT+1 [n]] S 8 + 32 log(26-1)
Putting together the developments so far, we have that with probability least 1 58, for all H' E [
H
H'
Qu(In,an) (x() < Var (V++1 xx] + 6 14 1og(22-))
h=1
< 38 + 142 (28-21))) 1)
42

---

Proof of Lemma G.8. Note that we have
Var(X²) = E[ -[x 2 (x = S < - [[X])*]
where the last line uses that |a² b2l - a bj for a. 11.
Proof of Lemma G.9. Abbreviate V = V* By telescoping, we can write
H' Var (V4-1 mm)]
ZH
h=1
H'
E (h+1(1n411 | [V=*(V++1 xnl)
H'
H
Ed [ (I/+1) [nn]
Vi (x +
Σ
vi (2x) - (I8" (V++1 2n1)2 + (1
- (2((x))
h=1
h=1
H'
Σ
E"
[ 1 (2h+1) [nn] V2 V (x
Σ
V2 (x%)
(EE" (V=+1 [xx1))2 1.
h=1
h=1
For the latter term, since la² - -b² < 2/a b) for a, b
[0, 1]. we have that
H'
H'
(2n)
(V++1 xx,))² S 2
V (xx)
[V æn]
h=1
LE" [rx xT]] S 2 Σ
E" [rk xn).
A=1
By Lemma D.3, we have that with probability at least 1 - 8, for all H' E [H].
H xn]
H'
3
3 + 1og((28-)) 2
B Br
+ 4 loglogg20 1)) 1
2
h=1
For the first term, by Lemma D.2, we have that for all 17 E (0,1), with probability at least 6, for all H' (H).
ET [V (xN+1) mn] (241(1141) S n
E
(V2t
EE (VA+) xxn])
(x641)
1n + +1 "log(00)
H
Var ( mm]] + - 1og(8-1)
h=l
H'
< 4m
Var [Vh+1 | xn) + + log(6-1)
h=1
4m + log(d-1)
where the last inequality uses Lemma G.8. Putting everything together and setting 17 1/8, conclude that with probability at least 25, for all H' [H]
1 ZH S - 7 + 16 16log(25 1) + 4,
which yields the result after rearranging.
43

---

G.2 Formal Statement and Proof of Theorem G.1
The following result shows that the dependence on the variance in Corollary 2.1 cannot be improved in general, which implies that the dorizon-dependence in this regime tight.
Theorem G.1 (Lower bound for stochastic experts). Consider the dense reward setting where Th E 00 1] and R = H. For any n E N. H E N and o² E [H, H there exists a reward-free MDP M with X 3 and |A| = 2. class of reward functions R with |R|= = and class of policies II with [II] = 2 with the following property. For any (online or offline) imitation learning algorithm, there exists deterministic reward function r = {ra)==l and expert policy x² E such that oz. S o² and μ S o² /H, and for which
PP -
1
Z
n
8
for an absolute constant è 2 1.
Beyond showing that a slow 1/ /n rate is required for stochastic policies, 21
Proof of Theorem G.1. For this proof, we consider a slightly more general online im- itation learning model in which the learner is allowed to select dj based on the sequence (ri, ai, ".,aa"")....... (2) tion learning model. Let H E N. n E N. and o² E [H. H²] be given. Fix parameter K E N such that H/K K is an integer and a parameter A E 1/2) be fixed; both parameters will be chosen the end of the proof.
1: -h oh-1)) (1/o axa)) at training time; this subsumes the offline imita-
We first specify the dynamics for the reward-free MDP M and the policy class IT. Let A = {a, b}. and let X (s, a, D). We consider the following (deterministic) dynamics. For h E H [L, K + 1, 2K + 1.. always the state is always In = s. For such a step h E H. choosing aø sets FA- = a for the next K -1 steps until returning to at time h K, and choosing on = b sets Ty = b until returning to s at time h + K (that is, the action has no effect for h & H).
We consider a class 11 = {x',, n' consisting of two experts n' and T². n" sets TH. (a s) = = + A
for & E H and sets nn (2) a for all h & H and a E X. Meanwhile, x" sets 7' s) = 2 + A for h H and sets T4 (x) = a for all h & H and x E X.
We consider two choices of reward function, r² and r". r" sets rí (s, a) = and rj (s. b)
0 for
E H. and sets rj (a. = and r (b.-) = for h E H. Meanwhile, r" sets (s, b) = and r (s, = 0 for h E H and sets r), (a. 0 and r,,((,,, (b. )) = 1 for h & H.
Let problem instance I (M* .r; x²) refer to tuple consisting of the reward-free MDP M reward function r {rr J- and an expert policy n². We consider four problem instances altogether: (M*,r",
r", T)), (M "M,"'' x²), (M*, r", T'), and (M*,r",
Let P' denote the law of o², ................................ o" when a when we exccute the algorithm on the underlying instance, and likewise for b (recall that the law does not depend on the choice of reward function, since this is not observed); let E*|-] and E.D denote the corresponding expectations. In addition, for any policy let 1p-'l denote the law of o (I1, 01, .... (IH a. when we execute in the online imitation learning framework and the expert policy is x n², and define pa"|" analogously.
We begin by lower bounding the regret. Consider a fixed policy मे { : X + A(X)), and let x (a) == [H] 1 Σnen (a(a s). Observe that for instance (M*, r rr)))) we have
J ( + + 2
fx s) = { + H - (7(a)) 2
H
K Σ MEW
Rajaraman al. [67] show that for the tabular setting, it is possible to achieve 1 1/n-type rate in-expectation for stochastic policies. Their result critically exploits the assumption that |X] and |Al are small and finite to argue that it is possible to build an unbiased estimator for x². Theorem G.I shows that such a result cannot hold with even constant probability for the same setting. We believe the fact that 1/n-type rate is even possible in expectation to be artifact of the tabular setting, and unlikely to hold for general policy classes.
44

---

and for instance (M (r",.r)) 1T),
- [ - - K
HZ(a) ( + 2 H..
Σ
(b(b
hCH
Likewise, for instance (M*, r², n²), we have
J 1 2
A
H
- K
Σ
s)) - A H
hER
and for instance (M1* r", x'),
-,~ = 2/ 2 -
- H H
Σ
(a
( - ) H Hl)
KCH
We conclude that for any 0, since the law of the dataset is independent of the choice of the reward function,
max
IP
(TT - J,r ž E H| (T)((T))
J 2
2H, -
EH
(
2
P
2 + - ( 2 E
P 7(a)
+
H H EH
2
max
11
P
H(a)H
H EH
H 2 2H
2
( +
( - 2
2
max
A
(a)
H eH
P
(Ta)
H 2 3H
2
2
2
1
1 +
2 }
max
A
((a)
IV
P
2 - 4
2
2
2
+
A
- (a)
N
4
2
2
2 4
1
(1-P))
1(
2
A
(a)
W
3
+
(a)
4
IV
2
1
[(
P
A
(a)
IV
+ P
(a))
4
2
1
(Iv(
4
where the second inequality uses the union bound (i.e. P[[e| 2 E| = P[s 2/ P(x 2
E| + 1 2 =)), and the second-to-last inequality holds long as E < A. In particular, this implies
that
AH
AH
P
J
P
J+(T')
(7)
2
max
2 7 (1 Drv(PP,)))
AH
AH
-
1 (+)
Next, using Lemma D.2 of Foster al. [36], can bound
n
DM Po) (P) <E'
Di
Observe that for a given episode i, regardless of how the policy F² selected:
The feedback for steps h & H is identical under pa and pp.
The feedback at step h E H differs only in the distribution of at ~ (') versus of ~ (s). This is cquivalently to Ber(1/2 + A) feedback versus Ber(1/2 A) feedback.
45

---

As result, using Lemma D.2 of Foster et al. [36] once more, we have
D parl"' p
S 7
DÅ (Ber(1// + A), Ber(1/2 A))
NEH
Since A E 10,1/2), we have (i + A); Ber(1/2 - A)) S 0(42) (e.g., Foster et al. [34,
Lemma A.7]). We conclude that
176| A2) = o
A
K
We set = If.. for > sufficiently small so that V Po) least one of the four problem instances, the algorithm must have
I 1/2, and conclude that on
HK
J(x') - 2 ((AH) = -
with probability at least 1/8.
Finally, we compute the variance and choose the parameter K. Observe that for all of the choices of
expert policy and reward function described above, have Q (I Rt" (x+)) Q% (oh, 0 for & H. while
@ (rh, xt (mn)) Q7 (I a) SK K
for h E H. so we can take z S K. Consequently, we have
H
2
Σ
E"
[0% (Kh, (xn)) 2h (Ih, an))²
S ΣE' [00 (s))*(s)) - Qh (s, an))
E
h=1
hEH
< K
K2 = HK.
We conclude by setting = 02/11, which admissible for o² E [1, 112| (up a loss absolute constants, we can assume that o² H an integer without loss of generality).
G.3 Additional Proofs
Proof of Proposition 3.1. We have
H
2
ET [1o (mnsan) Vi" (an)))²
h=1
Note that Q (0h, an) = |r + ViT (In+1)
2h: an]. Hence, by Jensen's 's inequality we can bound
ET [QX (Kh, Vn (sx))²
< E=
E (rh + Vitt (#n+1) V/," (xn))² Ih an
E (rn V VR (2x))) whh
E="
Var (r V 13
so that
H1
0² < E=
Var=" n' + Vit (Ix+1) Ih
1=
< Ex
V [Tn + Vii (IT41) 2m
"
rh < R2
where the second to last inequality follows from Lemma D.5.
46

---

Part II
Additional Results
H
Additional Lower Bounds
This section contains additional lower bounds that complement the results in Sections 2 and 3:
Appendix H.1 shows that the conclusion of Theorem H.1 continues to hold even for online imitation learning in active sample complexity framework.
Appendix H.2 presents an instance-dependent lower bound for stochastic experts, complementing the minimax lower bound in Theorem G.1.
Appendix H.3 investigates the extent to which Theorems 2.1 and 3.1 are tight per-policy basis.
H.1 Lower Bounds for Online Imitation Learning in Active Interaction Model
For the online imitation learning setting introduced in Section 1.1, we measure sample complexity in terms of the total number of episodes of online interaction, and expert feedback is available every episode. In this section, we consider more permissive sample complexity framework inspired by active learning [40, 75]. Here, as in Section 1.1, the learner interacts with the underlying MDP M through multiple episodes. At each episode E [m] the learner executes a policy x
(Ti. : X' - A(A)) and at any step in the episode, they can decide whether to query the expert for an action 0j Ty (2%) at the current state 2/- We M 1 the learner queries the expert at any point during episode i and set M' = 0 otherwise, and define the active sample complexity M the total number of queries.
M Σm=
It is clear that the active sample complexity satisfies S and in some cases might hope for it to be much smaller than the total number of episodes, at least for well-designed algorithm. While this indeed be the case for MDPs that satisfies (fairly strong) distributional assumptions [75], we will show that the lower bound in Theorem 2.2 continues to hold in this framework (up to logarithmic factor), meaning that online interaction in the active sample complexity framework cannot improve over LogL ossCos in general.
Theorem H.1 (Lower bound for deterministic experts in active sample complexity framework). For any m E N and E N, there exists reward-free MDP M with |X| [A| m + 1, a class of reward functions R with |R| m + 1, and class of deterministic policies with log II log (m) with the following property. For any online imitation learning algorithm in the active sample complexity framework that has sample complexity E[M] S m for an absolute constant c >> there exists a deterministic reward function = {rr) with Tı E [0, 1] and (optimal) expert policy T E IIl with μ such that the expected suboptimality lower bounded as
H
B[J(=t)-
m
for an absolute constant e > In addition, the dynamics, rewards, and expert policies are all stationary.
Since this example has log IT| = log( M), it follows that the sample complexity bound for LogLossBC in Theorem 2.1 (which uses A n)) can be improved by no more than log(n) factor through online interaction in the active framework.
Proof of Theorem H.I. Let m E and E N. be fixed. We first specify the dynamics for the reward-free MDP M* Set == (xI,..., Xm) and A = {a, b). The initial state distribution is Po unif
[x1, ... xm). The transition dynamics are Ph. x, a) T(x' = x) for all h;; that is, Ei....,.m all self-looping terminal states.
47

---

Let problem instance I = (M" x²) refer to tuple consisting of the reward-free MDP M reward function (ra k=1. and expert policy x². We consider + problem instances T I parameterized by a collection of policies II = { ".....,,TT"""""""""". and reward functions
R (r....,,?""
For problem instance I = (M*,""; ""*",,",)) x"), the expert policy is n², which sets (x) = a for all
x E X' and h E [H]. The reward function r sets rn (x, Ifa = a} for all E X and h E [M].
For each problem instance I' (M* r², T the expert policy is n², which for all h E [H]
sets Ti (x) = a for x * X, and sets T" (x,) = b. The reward function re sets TT a)
I[a a, x # x = b = x,3 for all [H].
Let J denote the expected reward under instance j. Note that all instances satisfy μ = 1, and that xf is an optimal policy for each instance j.
Going forward, we fix the online imitation learning algorithm under consideration and let Pr denote the law of o',...,0" when when we execute the algorithm on instance I;; let EE' [-] denote the corresponding expectation. In addition, for any policy म, let |=<l> denote the law of (#1, 01, aj) .i),,.... (IH, an, a when we execute ı in the online imitation learning framework when the underlying instance It, with the convention that az. =1 if the learner does not query the expert in episode j.
00
Our aim is to lower bound
max [T[((TT') [
jE (0......
Mnnn + a/h and p(T,,=') = (T,) To this end, define (J( 7') 2m=1 Be, (1 and observe that
1 m
H
E
En, tn (x,) (x,)
Illan # [
m
j=1
h=1
1
= =E x >
po p(f, 2
2m
2m
Next, note that for any E [m], if p( 7
l then Pj 2m
Pj(
T0)
<
2
which means that pj (ft x²) 2
H. It follows that
2
H 2m
H
([ E (2)
2
po
p( T³) <
2m
and if we define P = (mm) PP, then
H
H
(idii((mm)) ("' J'())
2
p
p(ā,
2m
2m
Combining these observations, we find that
H
H
H 2m
iE (0......m) ([1 2
max
po
(()
2
+ P
p(7,
<
4m
2m
H (Tv(F", PP).
4m
It remains bound the total variation distance. Next, using Lemma D.2 of Foster al. (36), can bound
n DI (p="ln"
Di (1P
DĀ (P IP) < Ey-unif[m]] [D [D P')] S 7 javuiil(m) [m]] E
p
Since the feedback the learner receives for a given episode is identical under instances I and I is identical unless i) x1 = xj. and ii) the learner decides to query the expert for feedback (i.e., M = 1). we can bound
D [x="|x" "p=""=",ppp'/11 pprrl1n)) < 1x [ar xj, M 1]
48

---

and hence
E [ EE
Σ
DH par ,p)l)
< 2
E undffi]m
E"
p 1 [ = Æラo M =1]
2 E
p p |m
[+c
x
X3j M --
m
2
E"
10 In*
[M
m
2
[EIM].
follows that if [M]] I m/56, then Drv (P",P) - 1/2, so that the algorithm must have
max B(J((T'- J( 2 8m (m....m
H.2 An Instance-Dependent Lower Bound for Stochastie Experts
In this section, further investigate the optimality of LogLossBC for stochastic experts (Theo- rem 3.1). Recall that when log [ O(1) the leading-order term in Theorem 3. scales as roughly
v 2 /n, where the salient quantity is the variance
H Σ
EE
[[OR (In, T (xx) Qi (Ih, an))
for the expert policy n². Theorem G.1 shows that this optimal qualitatively, in the sense that for any value o², there exists class of MDPs where the o I a², and where the minimax rate is at least o²2/n.
what follows, we will prove that for the special case of autoregressive MDPs (that is, the special case of the imitation learning problem in which the state takes the form 2n. a1:h-13 1: cf. Appendix B.3), Theorem G.1 is optimal on per-policy basis. Concretely, we prove a local minimax lower bound [28] which states that for any policy x* and any reward function r", there exists difficult "alternative" policy ग. such that in worst case over rewards r E [-r*, +r*} and expert policies π e { 7 any algorithm must have regret at least Vo2/n.
Theorem H.2. Consider the offline imitation learning setting, and let M* be autoregressive MDP. Let a reward function with Ek=1 ră [0, R] almost surely be fixed, and let an expert policy " be given. For any n E N, there exists an alternative policy t such that
P J()) (())
min max Aig #E(m" 33 rE(r"--")
max
2
for all n 2 d' where c' > 0 are absolute constants.
Theorem H.2 suggests that the leading term in Theorem 3.1 cannot be improved substantially without additional assumptions, on a (nearly) per-instance basis. The restriction to m 2 c' in Theorem H.2 is somewhat natural, this corresponds to the regime in which the Vo term in Theorem 3.1 dominates the lower-order term.
Proof of Theorem H.2. We begin by observing that for any A > 0.
min max max P[J,(T)= - J, (7) 2 A] min max P[IJ-- J,- 2 A]. Alg -E(=",3)
Alg xE(m",)) re((",-))
49

---

with the convention that (T) denotes the expected reward under r; we abbreviate J(T) J (x) going forward. Let F, denote the law of the offline imitation learning dataset under я. If we set J(T') - / then by the standard Le Cam two-point argument, we have that
max PT [[((T)) (( PI -
1 - PR - < A] ( J( 2 A))
IV. IV
2 (1 - -
J 2 Al)
2 - DTv PM PP 1 - n D |px PP*)
where the final inequality uses the standard tensorization property for Hellinger distance (e.g., Wainwright [91]).
We will proceed by showing that
Wa (E) == sup
Sup(1 (1())) J (TT D [ ,IPT)
S s=²] 2 ((() voz. =²,
(19)
for any & 0 sufficiently small, from which the result will follow by setting 8² 1/n and
arg max [J(T)) J(x")| D (P" ,P") S <=* 2 2((1 voz. e².
To prove this, we will appeal to the following technical lemma.
Lemma H.1. For any distribution Q and function h with [b|] S R almost surely, it holds that for all
S e² Varo[h] there exists a distribution such that 4R
Ep[h] - [g[h] 2-3 Varqllh
D ( P) E
Since stochastic policies æ autoregressive MDP M are equivalent to arbitrary joint laws over
the sequence 01.H (via Bayes' rule) and J(T) E
H E ră Lemma H.1 implies that for any
82 Var
[Σ m1 /4R2, there exists a policy सं such that (i) D (IP=", TPx) s DKL (Ix"
||xx)) s
e2, and (ii)
H Σ 1=1
J 2 2-
V T
.2.
h
This establishes Eq. (19). The result now follows by setting that n DH(""", Jpa) I 1/2, which is admissible whenever n n² Finally, we observe that for any deterministic MDP, by Lemma D.5,
for an absolute constant e >> 0 so
V Σ Th
E= Σ Var
[ + V (2)+1) Ih
E=
Σ ( (z), V/ (xn))²
since deterministic MDPs satisfy
QK (In, an) = rr(( ) + Viti(a44))
almost surely, and since E" [QX (In, an) |aa] = VE (xx).
Proof of Lemma H.1. Recall that we assume the domain is countable, so that Q admits a probability mass function q. We will define IP via the probability mass function
((
p(x) = Ege ((xx((()))))) ((x))en)()))
50

---

for parameter > 0. We begin by observing that
D log (Bo()))))) 17 Bolk log (Bs ( (ettn-Bo/MD]]
We now the following lemma.
Lemma H.2. For any random variable X with |X| S R almost surely and any E (0, (2/R)-1)
r Var[X] S log 1 log(BB(ool
S v/rVar(
Hence, as long as S (21)
( P) S / Varq(h).
We set min {
g² Varg
1
so that DKL Q P) - E².
[R]
2 f
Next, we compute that
0 S DKL (P| = n log (Bo [c"
so that
Eg(h] 2 21 log [e [M] = =1 log Re [enln-BolAD)
Ep [h]
Since < (2R)
Lemma H.2 yields
2 Varg [h] 8V Varg [h] E²
Ep]4] - Bglh] 2 8
long as ²² <
Varg [k]
Proof of Lemma H.2. Note that ex < + x (c - 2)x² < + x + x² whenever [æ]
S 1, and
similarly e" 2 1 for | I 1. It follows that if n $ (2R) -1
1 1
Var(X) < B E
< + 17+ Va)(X)
We conclude by using that log(1 + x) S x for I E [0.
H.3 Tightness of the Hellinger Distance Reduction
Theorem 2.1 and Theorem 3.1 are supervised learning reductions that bound the regret of any policy terms of its Hellinger distance D3 (IP p" to the expert policy π². The following result shows that these reductions are tight in fairly strong instance-depender sense: Namely, for any pair of policies के and ";, and for any reward-free MDP M*, it is possible to design a reward function
r r= H h= for which each term in Eq. (9) of Theorem 3.1 is tight, and such that Theorem 2. is tight; the only caveat is that we require the reward function to be Mon-Markovian, in the sense that Th depends on the full history 1ish and d1:k-
Theorem H.3 (Converse to Theorems 2.1 and 3.1). Let reward-free MDP M* and pair of (potentially stochastic) policies प and n be given.
1. For any R > 0, there exists a non-Markovian reward function = {ra) with ΣH
H
[0, R] such that
- > R
D (Pa. Pr').
(20)
51

---

2. For any o² > O, there exists a non-Markovian reward function r = {ru for which oz ==
11 ETT [Q%% (1ish 01.) Vi (I1:h a1:h-1)) o², and such that
1
- - J(T) 2 DR(PS, PP").
(21)
For any R > and o² > 0, there exists a non-Markovian reward function r {rr]i== with Σ Th E [0, R] and oz S o² simultaneously such that
1 min { Vo2 DH )r R. D (P², pa pot)) J(T))- 9
Eq. (20) shows that there exist reward functions with bounded range for which Theorem 2.1 and the lower-order term in Eq. (9) of Theorem 3.1 are tight, while Eq. (21) shows that there exist reward functions with bounded variance (but not necessarily bounded range) for which the leading term in Eq. or Theorem 3.1 is tight.
Note that for some MDPs, the state TA already contains the full history T1Ah-1 d1:h-1, so the assumption of non-Markovian rewards is without loss of generality, For MDPs that do not have this property, Theorem H.3 leaves open the possibility that Theorems 2.1 and 3.1 can be improved per-MDP basis.
Proof of Theorem H.3. Consider pair of measures and Q, and set P := (P + Q) Consider the function
1 1Q
= 1
[0. 1].
2 P
Using Lemma D.4, we observe that
Q
Ep [h] R2(M] [M]
2 F [M] - Re [h] = Re
Ep
(x
P.(..)). (22)
P
P
We also observe that by concavity of variance,
1 2 [Vrrph]] + Vare(h]) I Varplh]
)
( (Q =
2
Ep
E
< D IP.
(23)
To apply this observation to the theorem at hand, let a parameter B > 0 be given, let P 1 {(pr +I and consider the MarMar reward function that sets f1, . Ph-1 and
(T( = B (1 1
E [0. B). B).
2 p
Then by Eq. (22), we have that
B
J(x)) J(a*)-
D
6
At the same time, by Eq. (23), we have that
H
Var n
Σ rh
= Var
-Vr=*
[rm]
< 2B² D3 pá (.mppr))))
and by Proposition 3.1,
2 < "
Th
Note that since the reward function under consideration is non-Markovian, value functions Q and V, depend on the full history Fish 01:h-1.
52

---

To conclude, note that if we set B = RR², then Σx=1 1/h E [0, R] and
2 6
R
D
I )
Meanwhile, if we set
0²
B
2D lot)
then o 0²² and
J(T') J(T) 2 9 V
02 o2 D
Finally, if we set
0² 2D (P* p ^ R²
B
Then Σ Th [0, RR. o.. < 0² and
J(TT) { 2 6
B
D ( par
2 min
9 V 02. D2 (TR prr)),
R
Di (P=t pmr) (Pxx..r)))
6
I Benefits of Online Interaction
Our results in Sections 2 and 3 show that the benefits of online interaction in imitation learning- to the extent that horizon is concerned are more limited than previously thought. We expect that in practice, online interaction will likely lead to benefits, but only in problem-dependee dependent sense. To this end, we first discuss the role of misspecification and the realizability assumption used by our results, then highlight several special cases in which online interaction is indeed beneficial, but in policy dess-deeendent fashion not captured by existing theory. In particular, we identify three phenomena which lead to improved sample complexity: (i) representational benefits; (ii) value-bused feedbuck; and (iii) exploration. Our results in this section can serve as a starting point toward developing a more fine- grained understanding of algorithms and sample complexity of imitation learning.
L1 The Role of Misspecification
This paper (for both deterministic and stochastic experts) focuses on the realizable setting in which n' E II. It is natural ask how the role of horizon in imitation learning changes under misspecification, and whether online interaction brings greater benefits in this case. This is a subtle issue, as there are various incomparable notions of misspecification error which can lead different forms of horizon dependence. For example, for deterministic experts, if II is misspecified in the sense that inf wll Loc (TT) I Eapx. the indicator-loss behavior cloning algorithm in ?? achieves - & RH. [nn[([188")) + Eapx which is tight in general. In other words, the dependence on Eaox is not horizon- indieenddnnd On the other hand, as we show in Appendix E, if we assume that infzen x (pa || IP*) < Eapx. a stronger notion of misspecification error, then LogLossBC achieves Morizon-independerr independent guarantee of the form - < R [[og[[[[0=))
n
Eapx We leave a detailed investigation of tradeoffs between misspecification and horizon (as well as interplay with online versus offline IL. for future work; by giving the first horizon- inteepedennn treatment for the realizable setting, we hope that our results can serve as a starting point.
1.2
Representational Benefits
The classical intuition behind algorithms like Dagger and Aggrevate (which Definition 1.1 attempts to quantify) is recoverability: through online access, we can learn to correct the mistakes of an imperfect policy. Our results in Sections and 3 show that recoverability has limited benefits for stationary policy classes as far as horizon is concerned. In spite of this, the following proposition shows that recoverability can have pronounced benefits for representational reasons, even with constant horizon.
53

---

Proposition 1.1 (Representational benefits of online IL). For any N E N. there exists class M of MDPs with H = and a policy class II with log/ O(N) such that
There is an online imitation learning algoritlum that achieves J(x)) [(a) 0 with probability at least 1 6 using O(log(6 episodes for any MDP M E .M and expert policy x² E III In particular, this can be achieved by Dagger.
Any proper offline imitation learning algorithm requires n. = ( trajectories to learn non- trivial policy with J(x') - -() & for an absolute constant c > 0. 23
The idea behind this construction is as follows:
The behavior of the (stochastic) expert policy at step / = is very complex, and learning to imitate it well in distribution (e.g.. with respect to total variation or Hellinger distance) is a difficult representation learning problem (in the language of Section 2. e.g., Theorem 2.1, we must take log/IIı| very large in order to realize T)). For offline imitation learning, we have no choice but to imitate σं well at h 1. leading to the lower bound in Proposition I.1. With online access though, we can give up learning #f well, and instead learn to correct our mistake at step = For the construction in Proposition I.1, this a much easier representation learning problem, and requires very low sample complexity (i.e., we can realize gi with a class 1l2 for which log [وا] is small. We conclude that Dagger can indeed lead to substantial benefits over offline IL, but for representational reasons unrelated to horizon, and not captured by existing theory. While this example is somewhat contrived, suggests that potential to develop a deeper understanding of representational benefits in imitation learning, which we leave as promising direction for future work.
1.3 Benefits of Value-Based Feedback
Beginning with the work of Ross and Bagnell [71] on Aggrevate, many works (e.g., Sun et al. [78))
consider a value-based feedback variant of the online IL. framework (Section 1.1) where in addition to (or instead of) observing az the learner observes the expert's advantage function A (xx, ==
Q7 (Ih, x7 (z))) - Q% (Ia, .) or value function Q7 (æas .) at every state visited by the learner (see Appendix 1.5.2 for details, which are deferred to the appendix for space). While such feedback intuitively seems useful, existing theoretical guarantees-to the best of our snowledge-171, 78] only show that algorithms like Aggrevate are no worse than non-value based methods like Dagger, and do not quantify situations in which hasue-based feedback actually leads to improvement." 24
The following result shows that i) value-based feedback can lead to arbitrarily large improvement over non-value based feedback for representational reasons similar to Proposition I.1 (that is for complicated stochastic expert, learning to optimize a fixed value function can be much easier than learning to imitate the expert well in TV distance), but ii) it is only possible to exploit value- based feedback in this fashion under online interaction (that is, even if we annotate the trajectories for offline imitation learning with A (II, :) for the visited states, this cannot lead to improvement in sample complexity).
Proposition I.2 (Benefits of balue- feedback (informal)). For any N E N. there is a class of MDPs M with H and policy class II with log = O(N) such that
There is online imitation learning algorithu with value-based feedback that achieves J(x") J(²) = 0 with probability at least 1 using ( ")) episodes for every MDP M E M and expert n²* E II. In particular, this can be achieved by Aggrevate.
Any proper offline imitation learning algorithm (with value-based feedback) or proper online imitation learning algorithm (without valued-base -aased feedback) requires n S2(N) trajectories to learn a non-trivial policy with J(T)) ()) - -+)) (+)+ S cfrrr an absolute constant c > 0. 25
As with Proposition I.I, this example calls for a fine-grained policy class-dependent theory, which we hope to explore more deeply in future work.
We expect that this result extends to improper offline IL algorithms for which स & 11, but a more complicated construction is required; we leave this for the next version of the paper.
TThhse results reductions which bound regret in terms of different notions of supervised learning performance, which makes it somewhat difficult to compare them or derive concrete end-to-end guarantees. 25 As with Proposition 1.1, we expect that this lower bound can be extended to improper learners, but a more complicated construction is required.
54

---

1.4 Benefits from Exploration
A final potential benefit of online interaction arises in exploration. One might hope that with online access, we can directly guide the MDP to informative states that will help to identify the optimal policy faster. The following proposition gives an example in which deliberate exploration can lead to arbitrarily large improvement over offline imitation learning, as well as over naive online imitation learning algorithms like Dagger that do not deliberately explore.
Proposition 1.3 (Benefits of exploration for online IL), For any n E N and E N, there exists an MDP M and class deterministic policies II with [[]] 2 with the following properties.
1. There exists online imitation learning algorithm that returns policy ā such that ((*)) - ( = with probability at least 1 - using O(log(6-)) episodes, for all possible ll).
reward functions (i.e., even if
2. For any offline imitation learning algorithm, there exists a deterministic reward function {Tr and expert policy x* E 11 with B[J(=)) - J(R) 2 ((1) H. In addition, Dagger has regret [[J(=*) J(R)] 2 ((1) H
such that any algorithm must have
The idea behind this construction is simple: We take the lower bound construction from Theorem 2.2 and augment it with "revealing" which directly reveals the identity of the underlying expert. The true expert never visits this state, so offline imitation learning algorithms cannot exploit it (standard online IL algorithms like Dagger and relatives do not exploit the revealing state for the same reason), 26 but well-designed online IL algorithm that deliberately navigates to the revealing state can use it to identify x* extremely quickly.
As with the previous examples, this construction somewhat contrived, but it suggests that directly maximizing information acquisition may be a useful algorithm design paradigm for online IL, and we hope to explore this more deeply in future work.
I,5 Proofs
1.5.1 Proof of Proposition 1.1
Proof of Proposition 1.1. Let N E N be given. We set (x. [N] U {a. and
H 2. We consider family of problem instances {(M, x*, x²,r)) r)} indexed by subset S C [N] with
|S] =N/2 and an action a" E {a, bJ as follows. For a given pair (S,a*):
The dynamics are as follows. We have 21 = x deterministically. For simplicity, we assume that only actions in [N] are available at step h = 1. If E S, then 22 y. otherwise 22 = z.
The reward at step is ri(:.) = 0, and the reward at step 2 is given by ry = and r2(z, a) 1a J.
The expert n² sets x² xx) (T = (m, and n" (z) = a". -T
Let refer the problem instance above Is.a- {(Ms,a*, (., and let Js.a (T) denote the expected reward under this instance.
Upper bound for online imitation learning. Consider the algorithm that sets मं unif([NV] for each E [n]] If we play for n = logg (0%)) episodes, we will see x2 = 2 in at least one episode with probability at least 8, at which point will observe a" n (z), and we return the policy â that sets क (x) = ([VV) and (.) = ; this policy has zero regret.
Note that if we define II = ( eI=N/2.a=E(a.0) as the natural policy class for the family of instances above, then the algorithm above equivalent to running Dagger with the online learning algorithm that, at iteration i, sets
म unif ({ E 11,, TT(2)) a Vj < x = =
and choosing the final policy as के #' for any iteration i after 22 is encountered.
*TTis phenomenon is also distinct from "active" online imitation learning algorithms [75] which can obtain improved sampling complexity under strong distributional assumptions in the vein of active learning [40], but still do not deliberately explore.
55

---

Lower bound for offline imitation learning. Consider the offline imitation learning setting. When the underlying instance is Ls we observe dataset D consisting of n trajectories generated by executing "a in a The trajectories never visit the state so a* is not identifiable, and we can do no better than guessing a uniformly in this state. Letting Es,a- denote the law of D under instance Is we have e (f) मं (S x) + (S x) Z). It follows that for any S,
since the law of DD does not depend on a",
max Es,a- [Js.a (T'Sa.)) - Jssa (T) 2 Es (1 x) (5 xx)
(a,())
2 Es,al1 म ( x)].
Note that if न is proper in the sense that का (-x) US) for some 3 c [N] with ||| N/2,
have 1 - (S x) = |SSUS]. We conclude that if Ls [Js.er (TT - Js.a (f) S $. then Es,a [| 2 N. From here, follows from standard lower bounds for discrete distribution estimation (e.g., Canonne [18]) that any such estimator S requires worst-case choice of S.
S2(N) samples for
I.5.2 Background and Proof for Proposition I.2
Before proving Proposition 1.2, we first formally introduce the value-based feedback model we consider.
Background on value- based feedback. We can consider two models for imitation learning with value-based feedback, inspired by Ross and Bagnell [71], Sun et al. [78].
Offline setting. In the offline setting, we receive n trajectories (I ai)...., ( generated by executing n* in M For each state in each such trajectory, we observe A7, (Ik, where Ag (x,a) = 0% (z, x (x)) 2% (Ir, a) is the advantage function for x² .7
Online setting. The online setting is as follows. There are at episodes. For each episode i, we execute a policy म', and receive a "trajectory" o' = (# ai "."))...,, (I' dj ~ (xx)) and dz Ai ~ xt' (xi)). In addition, for each state in the trajectory, we observe A (æx, -). After the episodes conclude, we output final policy स on which performance is evaluated.
C'r: *-2) ), where
Proof of Proposition I.2. We only sketch the proof, as is quite similar to Proposition I.I. Let N E N be given. We set S = {x, y, y, A [N]. and H = 2. We consider class of problem instances ((M, ग* } indexed by sets Si, S2 C [N] with |S|| = |S2] = N/2 defined as follows. For given pair S2);
The dynamics are as follows. We have ø1 x deterministically. If af S1, then x2 = y, otherwise
I2 = z.
The reward function sets (x, 0, r2(y,) :) and r2(z, a) = Iiaa E S2). The expert n² sets x (x) (n: n (z) unif and (y) = unif([N]]
We refer to the problem instance above as Is. (Ms, T.. S2y denote the expected reward under this instance.
S2) Us S2), and let Js,. (T)
Upper bound for online imitation learning with value-based feedback. Consider an algorithm that sets मं ([V]( for each [n]. If we play for n = logz(ō episodes, we will see I2 in at least one episode with probability least 1 5, at which point we will observe AT (z,-). We can pick an arbitrary action with Ag" (z,-) and return the policy क that sets म (x) uni]( and 72 (-)
) = a; this policy has zero regret.
Note that if we define instances above, then the algorithm above is equivalent to running Aggrevate with the online learning algorithm that, at itcration i, sets
( ss) h -= as the natural policy class for the family of
# unif (f x E II, T2(2) E argmax A3 Vj < <i: =
27 Our results are not sensitive to whether the learner observes the advantage function or the value function itself; choose this formulation for concreteness.
56

---

and choosing the final policy as क = H' for any iteration i after I2 is encountered.
Lower bound for offline imitation learning. Consider the offline imitation learning setting. When the underlying instance is St we observe a dataset D consisting of trajectories generated by executing 55 in Ms, S2. The trajectories never visit the state so Sy is not identifiable, and we can do no better than guessing uniformly in this state. Letting E. denote the law of 'D under instance ,2, we have Ss (*) मi (S1 x) + Ri (S1 T2 S2 Z). It follows that for any (S1, S2), since the law of 'D does not depend on S2
max Es, 92 Js st) Js, [T) 2 Es [1 R1 x) - (S x)/2] Sa: Sa/////
Es, [1 - म. (Si x)]
with the convention that Es, denotes the law of D for arbitrary choice of S2. If मM is proper in the
sense that कं
(-x) un)f(S1) for some Si c [N] with |S] N/2, we have 1 (S x) =1
Ui). We conclude that if Es, Ss ss) - Js ( < g. then Es, N. From here, it follows from standard lower bounds for discrete distribution estimation (c.g.. Canonne [18]) that any such estimator S requires = (2NN samples for a worst-case choice of S.
>
Lower bound for online imitation learning without value-based- faseb-feedback. Consider an online imitation learning algorithm that does not receive value- feedback. We claim, via an argument similar to the one above, that the algorithm that ensures
Ss,.s [Js, (T') Js (f) S c
on all instances for a sufficiently small absolute constant c, then can be used to produce estimators S1, S2 C [N] such that with constant probability, either [S] ns| 2 N or |S2 n S2 2 g. N. From here, it should follow from standard arguments that this requires n = S2(N) samples for a worst-case choice of S) and S2.
1,5.3 Proof of Proposition 1.3
Proof of Proposition I.3. We consider a slight variant of the construction from Theorem 2.2. Let and H be given, and let A E (0, 1/3) be a parameter whose value will be chosen later. We first specify the dynamics for M* Set = (x, y, 2 and A = {a, c, The initial state distribution sets Po(x) 1 A and Po(y) A. The transition dynamics are:
Pa(a' = x x, a) = 11, T[(a E (a. b)) T2 I(a = cc. Pa(a') x. a) = T(x' 1x='=x] =x] x) for E (.
In other words, y and z are terminal states. For state x, actions a and b are self-loops, but action transitions to z.
The expert policies are n², which sets (x) = a for all h and x E X, and n², which sets n (x) and sets = (y) = o, (z) = b. We have II = (x",
m² r²) and and T (M* n², We consider two problem instances for the lower bound, I (M* (M*... For problem instance I', the expert policy is n' We set ri (x. (2, 0. (y, 1fa for all h. On the other hand, for problem instance I', the expert policy is T'. We set ri =
0, ri, (y.a) Hl b} for all h. Note that both of these choices for the reward function satisfy = 1, and that n² and x" are optimal policies for the respective instances. Let J denote the expected reward function for instance a, and likewise for b.
Upper bound on online sample complexity. We consider the following online algorithm. For episodes f l,...,:
If 2 f x, proceed to the next episode.
c = x, take action c, and observe 02 = T 7z)).. ). If 02 = a, return = n², and if 02 b, return
f n!
57

---

For any A e this algorithm will terminate after log(1/6) episodes with probability at least 1 - 8, and whenever the algorithm terminates, clear that π πτ. In particular, this leads zero regret for any choice of reward function.
Lower bound on offline sample complexity. By setting A x n? an argument essentially identical to the proof of Theorem 2.2 shows that any offline imitation learning algorithm must have
max E - (')) J(E) & AH
For the sake of avoiding repetition, we omit the details. Finally, we observe that since neither policy in II takes the action c, Dagger-when equipped with any online learning algorithm that predicts from a mixture of policies in II, such as in Proposition E.2) never take the action and hence subject the и lower bound from Theorem 2.2 as well.
58

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
59

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, other means that appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily architecture clearly and fully.
model architecture, the paper should describe the
(c) If the contribution is model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) recognize that reproducibility may tricky some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of
60

---

closed-source models, it may be that access to the model is limited in some way (e.g.. registered users). but it should be possible for other researchers have some path to reproducing or verifying the results.
Open access data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
This a primarily theoretical work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips (https://nips.cc//ublll) cctpsblicc/cccccccccccccccccc guides/Codeeubmi ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nip) http://iippscccpulllipe cc/public/ guides/CodeSubmi ssi ssionoolccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
61

---

The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics https::/neuring http://ss...ppplllcccccccceeeeee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
62

---

Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Question:
Answer: [NA]
Justification: This a primarily theoretical work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point that
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
63

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g.. CC-BY 4.0) should included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papersw thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
64

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
65


Reviews:
[{"review_id": "Wb9ghg2ILq", "reviewer": "Reviewer_2nRQ", "summary": "The paper proposes theoretical results on whether and when can offline imitation learning (IL) match online imitation learning in sample efficiency. The paper connects the results of existing works and demonstrates that offline IL can indeed match online IL under certain conditions. The paper further provides results on stochastic experts rather than deterministic experts.", "questions": "- Does the MDP assume finiteness?\n\t- If so, how would this result change under continuous action space with the most common parameterization (i.e. Gaussian policies)?\n- Does online IL algorithm include IRL?", "limitations": "- See above.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- As far as I know this is the first approach that leverages Hellinger distance on analyzing imitation learning methods.\n- The paper extends the BC results to stochastic policies under other function classes.\n\t- Interesting that online IL cannot really improve upon offline IL without further assumptions.\n- In addition to the theory the appendix provides experimentation that supports the theory.\n- The paper is very well written---I enjoyed reading the paper.", "weaknesses": "- The paper only considers log loss, which I understand is very commonly used, but I am curious about how much of these analyses transfer to other losses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> The paper only considers log loss, which I understand is very commonly used, but I am curious about how much of these analyses transfer to other losses.\n\nThis is a great question! Our analysis takes advantage of unique statistical properties of the log-loss (notably, that it provides *trajectory-level* control over deviations from pi*; see discussion in Sec 2.1.2). In general, other losses do not enjoy similar horizon-independent guarantees (for example, Ross & Bagnell ‘10 show that the indicator loss can have suboptimal horizon dependence, and it is straightforward to see that their counterexample also applies to the square loss and absolute loss). Indeed, one of the key findings of our paper is that using the log-loss is uniquely beneficial.\n\n\n> Does the MDP assume finiteness? If so, how would this result change under continuous action space with the most common parameterization (i.e. Gaussian policies)?\n\nNo, our results do not assume finiteness of the action space. Our analysis of Log-loss BC can be applied as-is to Gaussian policy parameterizations, as long as the realizability assumption in Assumption 1.1 holds.\n\n> Does online IL algorithm include IRL?\n\nThe formulation of online IL that we consider assumes that the learner has online/interactive access to both the MDP $M$ and expert $\\pi^{\\star}$. Typical IRL approaches use a less powerful access model in which we have online access to the MDP $M$ in the same fashion, but do not assume online access to $\\pi^{\\star}$ itself. Hence, all of the lower bounds for online imitation learning in our paper also apply to IRL.", "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": "", "extra_scores": {}}, {"review_id": "LD8nI82aFK", "reviewer": "Reviewer_meEq", "summary": "This paper studies the horizon dependence in imitation learning (IL). In particular, the authors analyze the sample complexity of Behavioral Cloning (BC) with logarithmic loss and general policy class $\\Pi$. \n\nFor deterministic experts, they first present a sharp horizon-independent regret decomposition and then provide a regret bound for BC. They show that BC achieves a linear horizon dependence under dense rewards when $\\log (|\\Pi|) = O (1)$, including stationary policies and policies with parameter sharing. Furthermore, they prove a lower bound, indicating that online IL cannot improve over offline IL with $|\\Pi|=2$.\n\nFor stochastic experts, they present a horizon-independent and variance-dependent regret decomposition and then give a regret bound for BC. This result shows that when $\\log (|\\Pi|) = O (1)$, BC can achieve a fully horizon-independent sample complexity in the sparse reward case. As for the dense reward case, BC requires a quadratic sample complexity, which is proven to be necessary in both offline and online settings.", "questions": "1. Theorem 2.4 implies that the slow $H/\\sqrt{n}$ rate for $\\sigma^2_{\\pi^*}=H^2$ is necessary in both offline and online IL. How can we reconcile this result with the claim in [2] that BC can achieve the $1/n$ rate for stochastic experts in the tabular setting?", "limitations": "The authors have adequately discussed and addressed the limitations of this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a new understanding of the horizon dependence in IL. Classical IL works show that the offline IL method BC suffers a quadratic horizon dependence, motivating various online IL approaches that attain improved linear horizon dependence. However, this paper proves that in certain cases, it is possible for BC to achieve linear horizon dependence and online IL cannot improve over offline IL, suggesting that there is no fundamental gap between offline IL and online IL.\n     \n2. This paper contributes new techniques for analyzing IL methods, which could be of independent interest. To attain a linear horizon dependence for BC, this paper presents a sharp horizon-independent regret decomposition. For deterministic experts, this regret decomposition is based on a novel trajectory-level analysis. For stochastic experts,  they provide an interesting information-theoretic analysis. I believe that these new techniques could inspire further advancements in IL theory.", "weaknesses": "1. Some formulas and claims in this paper are misleading. In the logarithmic loss of Eq. (5), the policy variable $\\pi (a^i_h|s^i_h)$ is written as a stationary policy, which does not include the case of non-stationary policies $\\Pi = \\Pi_1 \\times \\Pi_2 \\times \\cdots \\times \\Pi_H$ discussed in lines 242-248. Moreover, in Eq. (39) and Eq. (40) in Appendix E.1, the policy becomes non-stationary again, which is inconsistent with Eq. (5). As such, I suggest the authors to write logarithmic losses for stationary policies and non-stationary policies separately. Furthermore, in line 224, they claim that “This bound improves upon the guarantee for indicator loss behavior cloning in Eq.(3) by an O(H) factor”. This statement is a little problematic since the bound in Corollary 2.1 does **not** improve upon previous bounds for the case of non-stationary policies.\n2. This paper focuses on the horizon dependence in imitation learning. However, this paper misses a closely related work [1] that proves that a kind of IL method called adversarial imitation learning can achieve a horizon-independent sample complexity bound in a certain class of IL problems.\n\nReferences:\n\n[1] Xu et al., Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis, 2023.\n\n[2] Rajamaran et al., Toward the fundamental limits of imitation learning, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> Some formulas and claims in this paper are misleading. In the logarithmic loss of Eq. (5), the policy variable is written as a stationary policy, which does not include the case of non-stationary policies discussed in lines 242-248. Moreover, in Eq. (39) and Eq. (40) in Appendix E.1, the policy becomes non-stationary again, which is inconsistent with Eq. (5). As such, I suggest the authors to write logarithmic losses for stationary policies and non-stationary policies separately. \n\nOur results apply as-is to non-stationary policies. We believe this confusion is caused by a small typo, which is that Eq. (5) (as well as the first equation in App E.1) is intended to be stated with $\\log(1/\\pi_{h}(a_h | x_h))$, not $\\log(1/\\pi(a_h | x_h))$. We will be sure to include the `_h` subscript here and elsewhere in the final version of the paper.\n\n> Furthermore, in line 224, they claim that “This bound improves upon the guarantee for indicator loss behavior cloning in Eq.(3) by an O(H) factor”. This statement is a little problematic since the bound in Corollary 2.1 does not improve upon previous bounds for the case of non-stationary policies.\n\nThe statement “This bound improves upon the guarantee for indicator loss behavior cloning in Eq.(3) by an O(H) factor” is intended to convey that the bound improves upon Eq. (3) for *general* policy classes (which is true), not to claim that the bound offers a strict improvement on a per-policy class basis. While the paper already includes extensive discussion around this point (e.g., Page 6), we are happy to change the wording of the statement to make this as clear as possible.\n\n> This paper focuses on the horizon dependence in imitation learning. However, this paper misses a closely related work [1] that proves that a kind of IL method called adversarial imitation learning can achieve a horizon-independent sample complexity bound in a certain class of IL problems.\n\nThank you for pointing us to this work, which we are happy to cite and discuss in the final version of our paper. While the paper [1] does indeed contain some results concerning horizon-independence, their findings are quite restrictive compared to the results in our paper (in particular, unlike our work, their notion of horizon-dependence is not consistent with the standard notion consider in prior work on horizon-independent RL, e.g., Jiang & Agarwal ‘18). In more detail, their work:\n* Is restricted to tabular MDPs and policies (while our work considers general MDPs and function approximation).\n* Requires knowledge of the dynamics of the MDP (while our work considers the purely offline imitation learning setting, with no knowledge beyond expert trajectories).\n* Only achieves horizon-independence for a restricted class of MDPs called RBAS-MDPs (while our work achieves horizon-indepedence for *any MDP*, as long as the rewards are appropriately normalized). In particular, our notion of horizon-independence is consistent with that considered in Jiang & Agarwal ‘18 and subsequent work.\n\nThus, while the work of [1] is certainly related and we are happy to cite it, we believe that all claims of novelty and significance of our work stand.\n\n> Theorem 2.4 implies that the slow rate for is necessary in both offline and online IL. How can we reconcile this result with the claim in [2] that BC can achieve the rate for stochastic experts in the tabular setting?\n\nThis is a great question, which we discuss in Footnote 17. To restate here: Rajaraman et al. [2] show that for the tabular setting, it is possible to achieve a fast $1/n$-type rate in-expectation for stochastic policies. Their result critically exploits the assumption that |X| and |A| are small and finite to argue that it is possible to build an unbiased estimator for the expert policy $\\pi^\\ast$. Theorem 2.4 shows that such a result cannot hold with even constant probability for the same setting, thereby revealing a separation between the best rate that can be achieved in expectation versus the best rate that can be achieved in probability (note that since the expert is not assumed to be optimal, regret can be negative, which precludes the use of Markov’s inequality to convert an in-expectation bound into a bound in probability). \n\nMore broadly, we believe the fact that a 1/n-type rate is even possible in expectation for the tabular setting to be an artifact of the unique structure of this setting, and unlikely to hold for general policy classes or MDPs (e.g., for general policy classes, there is no hope of achieving unbiased estimation).", "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": "", "extra_scores": {}}, {"review_id": "ON1p0ln5OC", "reviewer": "Reviewer_DwTf", "summary": "This paper analyzes the sample complexity of offline behavior cloning w.r.t. the trajectory horizon. The theoretical result reveals that offline behavior cloning actually does not suffer more from the long horizon than the online BC, under two assumptions.", "questions": "N/A", "limitations": "See weakness.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The theory to further understand the complexity of BC is important.\n- The presentation is clear and easy to follow.", "weaknesses": "- The result is intuitive since with \"parameter sharing\", we assume the policy generalizes to longer horizon states.\n- One important assumption made in this paper, i.e. the policy class using parameter sharing, is unclear. For example, how the parameter sharing will affect practical learning? Does it introduce any bias for the policy learning?\n- The experiments are not solid. For example, the Atari figure seems like the Expected regret is random w.r.t. horizon. It is natural to question whether the MuJoCo results really fit the theoretical prediction or simply are due to the task properties.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> The result is intuitive since with \"parameter sharing\", we assume the policy generalizes to longer horizon states.\n\nWhile it is certainly intuitive that smaller policy classes yield improved rates, we emphasize that our work is the first to demonstrate that under the assumption of parameter sharing, horizon-free regret is possible with BC in general MDPs; we would like to push back on the idea that it is intuitive that this result holds in such generality, as this finding runs counter to the intuition expressed in many prior works. In particular, one of the key consequences of our work is that under the assumptions of parameter sharing and sparse rewards, the key challenge of compounding error is not present in BC when using Log loss, a finding which we believe is somewhat surprising in light of previous work.\n\n\n> One important assumption made in this paper, i.e. the policy class using parameter sharing, is unclear. For example, how the parameter sharing will affect practical learning? Does it introduce any bias for the policy learning?\n\nWe would like to emphasize that parameter sharing is not actually an “assumption” in our paper, but rather is an important special case of our general results.  Indeed, our main results hold in the general case of arbitrary policy classes (Theorems 2.1 and 2.3). Nonetheless, we emphasize that parameter sharing is a natural assumption in practice, and is satisfied whenever the expert policy is stationary with respect to time, which commonly occurs in application domains such as robotics and transformers. Indeed, if parameter sharing does not hold, it means we are training a completely different policy for each step $h$, which is rarely, if ever, done in practice.\n\nWe mention in passing that beyond its practical relevance, parameter sharing is a useful special case to isolate the effect that horizon has on offline imitation learning, in the sense that it illustrates the possibility of horizon-free rates.\n\n\n> The experiments are not solid. For example, the Atari figure seems like the Expected regret is random w.r.t. horizon. \n\nRegarding the Atari experiments, we emphasize that Figure 1b and 3b show a a clear trend where the regret with 200 trajectories decreases uniformly as the horizon increases, a demonstration that is amplified by the lack of overlap in the confidence intervals (which is consistent with our theory as we prove that the regret should not increase with horizon). Note that this empirical setup is consistent with our theory, as we have a stationary expert and sparse rewards, and thus expect the regret to be non-increasing with respect to horizon. If the reviewer can clarify why they believe the expected regret is \"random\" w.r.t. horizon for these experiments, we would greatly appreciate it.\n\n\nPerhaps the only surprising feature of the Atari experiments is that the regret is actually *decreasing* with horizon (as opposed to being non-increasing). To understand this, note that our theory provides horizon-agnostic upper bounds independent of the environment. Our lower bounds are constructed for specific worst-case environments, and do not rule out the possibility of improved performance with longer horizons environments with favorable structure. We conjecture that this phenomenon is related to the fact that longer horizons yield fundamentally more data, as the total number of state-action pairs in the expert dataset is equal to nH. In the final version of the paper, we will expand the discussion around this phenomenon, but we would like to emphasize that in no way do our experimental results conflict with the theory established in the rest of the paper.\n\n> It is natural to question whether the MuJoCo results really fit the theoretical prediction or simply are due to the task properties.\n\nWe are a little confused by this point, but would be more than happy to respond if the reviewer would be willing to further elaborate and clarify why they feel that the MuJoCo results do not fit the theoretical prediction, or explain which task properties they are concerned with.", "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": "", "extra_scores": {}}, {"review_id": "cnD6DsaUrE", "reviewer": "Reviewer_FtQL", "summary": "This paper presents a thorough analysis of imitation learning (IL), focusing on the gap between offline and online IL. The authors demonstrate that behavior cloning (BC) with logarithmic loss can achieve horizon-independent sample complexity under specific conditions, providing valuable insights into the theoretical underpinnings of IL.", "questions": "**Experiments:**\n\n- There is a gap between the developed theory and practice. It is not safe to conclude that the theory can explain the empirical results in Figure 1. There are possible theoretical explanations for empirical results that differ from this paper. Specifically, [1] showed that MuJoCo locomotion controls have deterministic transitions, thus the statistical estimation error comes from the initial step, and there are no compounding errors. The reviewer believes the explanation provided in [1] is also true for the studied Atari environments.\n- The reviewer believes that practitioners choose stationary policies in practice because the MDP formulation for practical tasks has stationary transitions, rather than the non-stationary ones studied in this paper. For stationary-transition MDPs, the estimation error is, in fact, smaller.\n\n**Related Work:**\n\n- [2] studied that adversarial imitation learning algorithms can achieve horizon-free sample complexity for structured MDPs. Their results are also important for understanding the horizon in imitation learning. This work should be reviewed.\n\n[1] Li, Ziniu, et al. \"Rethinking ValueDice: Does it really improve performance?.\" *arXiv preprint arXiv:2202.02468* (2022).\n\n[2] Xu, Tian, et al. \"Understanding adversarial imitation learning in small sample regime: A stage-coupled analysis.\" *arXiv preprint arXiv:2208.01899* (2022).", "limitations": "To the reviewer's understanding, this paper mainly focuses on the model selection problem under general function class approximation. This does not provide many new insights on the compounding errors issues and horizon dependence issues in imitation learning. The title may be revised to reflect the contribution.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper presents extensive theoretical results for offline IL and online IL under the general function approximation class. It builds a sharp separation between offline and online algorithms, which the reviewer appreciates a lot.\n- The reviewer believes that the analysis tools in this paper can be further applied in future studies of imitation learning and sequential decision making.", "weaknesses": "- The theoretical results have a gap with practice. For example, the reviewer finds it odd that the conclusion of a 'horizon-free' guarantee is obtained by assuming the policy class is well-controlled. Practitioners often choose a large function class to ensure the approximation error is small. \n- Some key related work is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.\n\n> The theoretical results have a gap with practice. For example, the reviewer finds it odd that the conclusion of a 'horizon-free' guarantee is obtained by assuming the policy class is well-controlled. Practitioners often choose a large function class to ensure the approximation error is small.\n\nWe assume that the reviewer is referring to the fact that our results assume realizability and scale with the complexity of the policy class. We remark:\n\n- Realizability is a standard assumption in RL theory, and is used as a starting point for virtually all existing theoretical results, cf. “Reinforcement learning: Theory and algorithms” (Agarwal, Jiang, Kakade, and Sun).\n\n- Our main results (Theorems 2.1 and 2.3) do not assume that $\\Pi$ is well controlled. Rather, these theorems are *reductions* (in the spirit of prior work on IL) showing that $H$-independent rollout performance is achievable when an appropriate notion of supervised learning error is small. Thus if the policy $\\hat{\\pi}$ has good supervised learning performance (regardless of whether it belongs to a finite class or enjoys a provable generalization bound), our theorems imply that it will have good rollout performance. Corollaries 2.1 and 2.2 instantiate these results for finite classes for concreteness.\n\n- We note that prior work does not achieve $H$-free guarantees *even in the case where $\\Pi$ is well controlled*. Our results show that with properly normalized rewards, generalization error of $\\Pi$ is the *only* source of $H$ dependence. In some sense, this is the strongest guarantee one might hope for, as the complexity of $\\Pi$ influences regret even absent sequential structure in the IL problem. For stationary policies with parameter sharing, our results can be instantiated to give end-to-end guarantees with no dependence on $H$.\n\n- Our most general guarantees for LogLossBC (see Appendix E and Theorem E.1) support infinite policy classes and misspecification, allowing one to trade off policy class complexity with approximation error. The conclusion is the same as for our main results: As long as the supervised learning error (policy class complexity + approximation error) is small, the rollout performance will be horizon-independent.\n\n> Some key related work is missing. [2] studied that adversarial imitation learning algorithms can achieve horizon-free sample complexity for structured MDPs. Their results are also important for understanding the horizon in imitation learning.\n\nThank you for pointing us to this work, which we are happy to discuss in the final version. While [2] contains results concerning $H$-independence, their findings are quite restrictive compared to our paper ( e.g. their notion of horizon independence is not consistent with that in prior work in RL, e.g., Jiang & Agarwal ‘18). Also, their work:\n- Is restricted to tabular MDPs and policies (while our work considers general MDPs and function approximation).\n- Requires knowledge of the dynamics of the MDP (while our work considers the purely offline imitation learning setting, with no knowledge beyond expert trajectories).\n- Only achieves horizon-independence for a restricted class of MDPs called RBAS-MDPs (while our work achieves horizon independence for *any MDP*, as long as the rewards are appropriately normalized).\n\nWhile the work of [2] is related and we are happy to cite it, we believe that all claims of novelty and significance of our work stand.\n\n> There is a gap between the developed theory and practice. It is not safe to conclude that the theory can explain the empirical results in Figure 1. There are possible theoretical explanations for empirical results that differ from this paper. Specifically, [1] showed that MuJoCo locomotion controls have deterministic transitions, thus the statistical estimation error comes from the initial step, and there are no compounding errors. The reviewer believes the explanation provided in [1] is also true for the studied Atari environments.\n\nWe emphasize that our experiments are intended to *validate* our theory, particularly the claim that log-loss BC can achieve $H$-independence. We do not claim at any point in the paper that our theory predicts the precise behavior in Figure 1; rather, we claim that Figure 1 validates the theoretical prediction that regret does not degrade as a function of horizon.\n\nRegarding the point about deterministic transitions in MuJoCo and Atari, we emphasize that even if dynamics are deterministic, one can still experience compounding errors due to stochasticity in the *learned policy*. This phenomenon has been widely observed [11,15, 39].\n\n> The reviewer believes that practitioners choose stationary policies in practice because the MDP formulation for practical tasks has stationary transitions, rather than the non-stationary ones studied in this paper. For stationary-transition MDPs, the estimation error is, in fact, smaller.\n\nWe believe there may be some confusion here.  A key feature of our analysis is that it supports both non-stationary *and* stationary policies (note that while we use the notation $\\pi_h$ throughout the paper, stationary policies are simply a special case in which $\\pi_h=\\pi$ for all $h$), and we state a number of improved guarantees special to *stationary* policies, e.g. discussion at the bottom of page 6. If the reviewer has a specific question regarding these results that we can clarify, we would greatly appreciate it.\n\n> To the reviewer's understanding, this paper mainly focuses on the model selection problem under general function class approximation. This does not provide many new insights on the compounding errors issues and horizon dependence issues in imitation learning. The title may be revised to reflect the contribution.\n\nWe believe this summary is misguided; please see the response to question #1.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper challenges the existing orthodoxy about imitation learning (IL), which says that the performance of behavioural cloning scales unfavourably in the problem horizon. The paper shows that BC is in fact a competitive IL algorithm when trained using the log loss. This has large practical significance since, in many practical settings, BC is the first (and sometimes only) algorithm that can be shipped.

In the AC-reviewer discussion, one reviewer pointed out concerns about clarity of the writing - please try to have the paper proofread again before submitting the camera-ready version.
Decision: Accept (spotlight)