Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning

Authors: dylan j foster
adam  block
dipendra  misra
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:44:43

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.

Main paper: 
 introduction: 
 Imitation learning (IL) is the problem of emulating an 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 is 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 it 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 (NeurIPS 2024). Figure 1 : Suboptimality of a policy learned with log-loss behavior cloning (LogLossBC) as a 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 horizon-independent. (a) Continuous control with MuJoCo environment Walker2d-v4. (b) Discrete control with Atari environment BeamRiderNoFrameskip-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 AI [46, 90] . Imitation learning also offers a conceptual framework through which to study autoregressive language modeling [21, 13] , and a 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 general-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 on 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 or infeasible in many applications, and offline imitation learning remains a 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 is fundamental. We ask:Is online imitation learning truly more sample-efficient than offline imitation learning, or can existing algorithms or analyses be improved?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-theoretic 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 = (X , A, P, r, H) consists of a (potentially large) state space X , action space A, horizon H, probability transition function P = {P h } H h=0 , where P h : X × A → ∆(X ), and reward function r = {r h } H h=1 , where r h : X × A → R. A (randomized) policy is a sequence of per-timestep functions π = {π h : X → ∆(A)} H h=1 . The policy induces a distribution over trajectories (x 1 , a 1 , r 1 ), . . . , (x H , a H , r H ) via the following process. The initial state is drawn via x 1 ∼ P 0 (∅), 1 then for h = 1, . . . , H: a h ∼ π(x h ), r h = r h (x h , a h ), and x h+1 ∼ P h (x h , a h ). For notational convenience, we use x H+1 to denote a deterministic terminal state with zero reward. We let E π [•] and P π [•] denote expectation and probability law for (x 1 , a 1 ), . . . , (x H , a H ) under this process, respectively. 2The expected reward for policy π is given by J(π) := E π H h=1 r h , and the value functions for π are given by V π h (x) := E π H h ′ =h r h ′ | x h = x and Q π h (x, a) := E π H h ′ =h r h ′ | x h = x, a h = a . 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 H h=1 r h ∈ [0, R] for a parameter R > 0 [47, 94, 104, 48] . We refer to the setting in which r h ∈ [0, 1] for all h ∈ [H], which is the focus of most prior work [70, 72, 71, [67] [68] [69] 80] , as the dense reward setting, which has R ≤ H; we will frequently specialize our results to this setting.Let π ⋆ = {π ⋆ h : X → ∆(A)} H h=1 denote the expert policy. In the offline imitation learning setting, we receive a dataset D = {o i } n i=1 of (reward-free) trajectories o i = (x i 1 , a i 1 ), . . . , (x i H , a i H ) obtained by executing π ⋆ in the underlying MDP M ⋆ . Using these trajectories, our goal is to learn a policy π such that the rollout regret J(π ⋆ ) -J( π) to π ⋆ 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 π ⋆ := {π ⋆ h : X → A} H h=1 is deterministic. For a userspecified policy class Π ⊂ {π h : X → ∆(A)} H h=1 , the most basic version of behavior cloning [70] solves the supervised classification problem π = arg min π∈Π n i=11 H H h=1 I{π h (x i h ) ̸ = a i h } =: L bc (π). 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, we make a standard realizability assumption (e.g., Agarwal et al. [2] , Foster and Rakhlin [33] ).Assumption 1.1 (Realizability). The policy class Π contains the expert policy, i.e. π ⋆ ∈ Π.This assumption asserts that Π is expressive enough to represent the expert policy. Depending on the application, Π 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 a 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 on finite classes with |Π| < ∞ [2, 33] .To proceed with analyzing the behavior cloning algorithm, a standard uniform convergence argument implies that if we define L bc (π) = 1H H h=1 P π ⋆ [π h (x h ) ̸ = π ⋆ h (x h )],then with probability at least 1δ, behavior cloning hasL bc ( π) ≲ log(|Π|δ -1 ) n .Meanwhile, a standard error analysis for BC leads to the following bound on rollout performance:EQUATIONCombining these bounds, we conclude thatEQUATIONFor the dense reward setting where R = H, this leads to quadratic dependence on horizon; that is, Ω(H 2 ) trajectories are required to achieve constant accuracy. Unfortunately, both steps in this argument are tight in general:• The generalization bound L bc ( π) ≲ log(|Π|δ -1 ) n is tight even when |Π| = 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-priori that the generalization error would decrease with H; alas, this does not occur due to the dependence between samples in each trajectory.• Ross and Bagnell [70] show that the inequality J(π ⋆ ) -J( π) ≲ RH • L bc ( π) 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 π ⋆ to the state distribution of π.Combining, these observations, it is natural to conclude that offline imitation learning is fundamentally harder than supervised classification, where linear dependence on horizon might be expected (e.g., with H independent prediction tasks).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 to 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 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 π ⋆ is given by 4Under recoverability, the Dagger algorithm of Ross et al. [72] leverages online interaction by interactively querying the expert and learning to correct mistakes on-policy, leading to sample complexityEQUATIONfor any finite class Π and deterministic expert policy π ⋆ (for completeness, we include an analysis in Appendix E.2; see Propositions E.1 and E.2). For the dense reward setting where R = H, we can have µ = H 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 of an approach that improves upon Eq. ( 3) for general finite classes).The improvements of online IL notwithstanding, Eq. ( 2) is known to be tight for BC, but this is an algorithm-dependent (as opposed to information-theoretic) 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 Π? While prior work has investigated this question for tabular and linear policies [67] [68] [69] , we approach the problem from a new (learning-theoretic) perspective by considering general policy classes.We present several new results that clarify the role of horizon in offline and online imitation learning.Parameter Sharing (Corollary 2.1)No Parameter Sharing (Π = Π1 × • • • ΠH ) (e.g., [70] )Sparse Rewards O R log(|Π|) n O HR log(max h |Π h |) n Dense Rewards (R = H) O H log(|Π|) n O H 2 log(max h |Π h |)n 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, Π 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-independent 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 payoffs is normalized, and (ii) an appropriate notion of supervised learning complexity for the policy class is controlled. Our result is facilitated by a novel information-theoretic 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 it is possible to 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 a 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 a 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) LogLossBC-through our variance-dependent analysis-can 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 LogLossBC without further assumptions on the policy class. Our results are summarized in Table 2 .Toward a learning-theoretic understanding of imitation learning. Our findings highlight the need to develop a fine-grained, problem-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. As a first step in this direction, we highlight several under-explored mechanisms through which online IL 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 to the appendix due to space constraints), we complement our theoretical results with an empirical demonstration of the horizon-independence 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-for example, an agent walking for a set number of timesteps-and use an expert trained according to RL to 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 is independent or improving with horizon, consistent with our theoretical results. We also perform simplified experiments on autoregressive language generation with transformers. Here, we 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 x ∈ ∆(X ) to denote the direct delta distribution, which places probability mass 1 on x. We adopt standard big-oh notation, and write f = O(g) to denote that f = O(g • max{1, polylog(g)}) and a ≲ b as shorthand for a = O(b).2 Horizon-Independent Analysis of Log-Loss Behavior CloningThis section presents the first of our main results, a horizon-independent 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. 
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 Π, we minimize the logarithmic loss:EQUATION)This scheme is ubiquitous in practice [45, 31] , and forms the basis for autoregressive language modeling [64] ; we refer to it as LogLossBC. We will show that this seemingly small changemoving from indicator loss to log loss-has significant benefits. Following the classical tradition of imitation learning [70, 72, 71] , our analysis proceeds via reduction to supervised learning. We first show that LogLossBC satisfies an appropriate supervised learning guarantee, then translate this into rollout performance. Our starting point is to observe that LogLossBC, via Eq. ( 4), can be interpreted as performing maximum likelihood estimation over the set {P π } π∈Π in order to estimate the law P π ⋆ over trajectories under π ⋆ (see Appendix E.1 for details). As a result, standard guarantees for maximum likelihood estimation [89, 102] imply convergence in distribution whenever π ⋆ ∈ Π. To be precise, define the squared Hellinger distance for probability measures P and Q byD 2 H (P, Q) = √ dP- √ dQ 2 .Then for any finite policy class Π, we have the following guarantee. 5Proposition 2.1 (Supervised learning guarantee for LogLossBC (special case of Theorem E.1)). For any (potentially stochastic) expert π ⋆ ∈ Π, the LogLossBC algorithm ensures that with probability at least 1δ,D 2H P π , P π ⋆ ≤ 2 log(|Π|δ -1 ) n .That is, by performing LogLossBC, we are implicitly estimating the law P π ⋆ ; note that this result holds even if π ⋆ is stochastic, as long as π ⋆ ∈ Π. We will focus on finite, realizable policy classes throughout this section to simplify presentation as much as possible, but guarantees for infinite classes under misspecification are given in Appendix E.1.We first consider the case where the expert π ⋆ is deterministic. Our main result is the following theorem, which translates the supervised learning error D 2 H P π , P π ⋆ into a bound on rollout performance in a horizon-independent fashion. Theorem 2.1 (Horizon-independent regret decomposition (deterministic case)). For any deterministic policy π ⋆ and potentially stochastic policy π,EQUATIONThis result shows that horizon-independent bounds on rollout performance are possible whenever (i) rewards are appropriately normalized, and (ii) the supervised learning error D 2 H P π , P π ⋆ is appropriately controlled. It is proven using novel trajectory-level control over deviations between π and π ⋆ ; we will elaborate upon this in the sequel. We emphasize that this result would be trivial 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/n-type rates and linear horizon dependence. We further remark that this reduction is not specific to LogLossBC, and can be applied to any IL 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 π ⋆ ∈ Π, the LogLossBC algorithm in Eq. ( 4) ensures that with probability at least1 -δ, J(π ⋆ ) -J( π) ≤ 8R • log(2|Π|δ -1 ) n .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 indicatorloss behavior cloning in Eq. ( 2) by an O(H) factor, and improves upon the guarantee for Dagger in Eq. ( 3) (replacing H with R ≤ H under r h ∈ [0, 1]) in the typical regime where µ = Ω(1).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|Π| = O(1), the bound in Corollary 2.1 is independent of horizon in the case of sparse rewards (R = O(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 Π, as long as log|Π| is appropriately controlled and realizability holds. This runs somewhat counter to intuition expressed in prior work [70, 72, 71, [67] [68] [69] 80 ], but we will show in the sequel that there is no contradiction.Generally speaking, we expect to have log|Π| = O(1) if Π consists of stationary policies or more broadly, policies with parameter sharing across steps h ∈ [H] (as is the case in transformers used for autoregressive text generation). As an example, for a tabular (finite state/action) MDP, if Π consists of all stationary policies, we have log|Π| = |X | log|A|, so Corollary 2.1 givesJ(π ⋆ ) - J( π) ≲ R|X | log(|A|δ -1 ); that is, stationary policies can be learned with horizon-independent samples complexity under sparse rewards and linear dependence on horizon under dense rewards. Similar behavior holds for non-stationary policies with parameter sharing (e.g., log-linear policies of the form π h (a | x) ∝ exp(⟨ϕ h (x, a), θ⟩)); see Appendix E.1 for details.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Π = Π 1 × Π 2 • • • × Π H ), we expect log|Π| = O(H) (more generally, D 2 H P π , P π ⋆ = O(H/n)).For example, in a tabular MDP, if Π consists of all non-stationary policies, we have log|Π| = H|X | log|A|. In this case, Corollary 2.1 gives linear dependence on horizon for sparse rewards (J(π ⋆ ) -J( π) ≲ RH|X | log(|A|δ -1 )) and quadratic dependence on horizon for dense rewards (J(π⋆ ) -J( π) ≲ H 2 |X | log(|A|δ -1 )). The latter bound is known to be optimal [67] for offline IL.We now investigate the optimality of Theorem 2.1 and discuss implications for online versus offline imitation learning, as well as connections to prior work. Our main result here shows that in the dense-reward regime where r h ∈ [0, 1] and R = H, Theorem 2.1 cannot be improved when log|Π| = O(1)-even with online access, recoverability, and known dynamics. with r h ∈ [0, 1] (in particular, R ≤ H) and (optimal) expert policyπ ⋆ ∈ Π with µ = 1 such that E[J(π ⋆ ) -J( π)] ≥ c • Hn for an absolute constant c > 0. In addition, the dynamics, rewards, and expert policies are stationary.Together, Theorems 2.1 and 2.2 show that without further assumptions on Π, online imitation learning cannot improve upon offline imitation learning in the realizable setting. That is, even if recoverability 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] [68] [69] 80] ? The important distinction here is that online IL can still improve on a 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 ∈ [H]. Let Π h := {π h | π ∈ Π} denote the projection of Π onto step h. In Appendix E.2, we prove the following refined guarantee for a variant of Dagger based on the log-loss (LogLossDagger). Proposition 2.2 (Special case of Proposition E.2). When π ⋆ ∈ Π is deterministic, LogLossDagger ensures that with probability at least1 -δ, J(π ⋆ ) -J( π) ≲ µ • H h=1 log(|Π h |Hδ -1 ) n .For classes with no parameter sharing (i.e., product classes whereΠ = Π 1 × Π 2 • • • × Π H ), we have H h=1 log|Π h | = log|Π|. In this case, Proposition 2.2 scales as J(π ⋆ ) -J( π) ≲ µ • log(|Π|Hδ -1 )n , improving on the bound for LogLossBC in Theorem 2.1 by replacing R with µ ≤ R. Thus, online IL can indeed improve over offline IL 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 IL for the special case of non-stationary tabular policies (where Π is a product class with log|Π| ∝ H) under dense rewards. However, for classes with parameter sharing (i.e., where log|Π h | ∝ log|Π|), the bound in Proposition 2.2 scales as µH log|Π| n , which does not improve over Theorem 2.1 unless µ ≪ 1. Since virtually all empirical work on imitation learning uses parameter sharing across steps h ∈ [H], we believe the finding that online IL does not improve over offline IL in this regime is quite salient. Nevertheless, it is important to emphasize that there are various practical considerations (e.g., misspecification or geometric structure) which this result may not account for. 62.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 a pair of potentially stochastic policies π and π ′ , defineEQUATIONwhere we use the shorthand a ′ 1:H ∼ π ′ (x 1:H ) to indicate that a ′ 1 ∼ π ′ (x 1 ), . . . , a ′ H ∼ π ′ (x H ). We begin by showing (Lemma F.2) that for all (potentially stochastic) policies π ⋆ and π, J(π ⋆ ) -J( π) ≤ R • ρ(π ⋆ ∥ π). We then show (Lemma F.3) that whenever π ⋆ is deterministic, Hellinger distancesatisfies 7 D 2 H P π , P π ⋆ ≥ 1 4 • ρ( π ∥ π ⋆ ).Finally, we show (Lemma F.1) that the trajectory-level distance is symmetric, i.e. ρ( π ∥ π ⋆ ) = ρ(π ⋆ ∥ π). This step is perhaps the most critical: by considering trajectory-level errors, we can switch from the state distribution induced by π to that of π ⋆ 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 is 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 an algorithm that minimizes an empirical analogue of the trajectory-wise distance in Eq. ( 6), and show that it leads to a bound similar to Corollary 2.1 (i.e., linear-in-H sample complexity under dense rewards). Relative to this work, our contributions are threefold: (i) we show that horizon-independent 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. 
horizon-independent analysis of loglossbc for stochastic experts: 
 In this section, we turn out attention to the general setting in which the expert policy π ⋆ is stochastic. Stochastic policies are widely used in practice, where they are useful for modeling multimodal behavior [76, 25, 14] , but have received relatively little exploration in theory beyond the work of Rajaraman et al. [67] for tabular policies. 8 Our main result for this section is a regret decomposition based on the supervised learning error D 2 H P π , P π ⋆ that is horizon-independent and variance-dependent [107, 106, 93] . To state the result, define σ 2 π ⋆ :=H h=1 E π ⋆ (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2as the variance for the expert policy. Theorem 3.1 (Horizon-independent regret decomposition). Assume R ≥ 1. For any pair of (potentially stochastic) policies π ⋆ and π and any ε ∈ (0, e -1 ),EQUATIONApplying this result with LogLossBC leads to the following guarantee.Corollary 3.1 (Regret of LogLossBC). For any π ⋆ ∈ Π, the LogLossBC algorithm in Eq. ( 4) ensures that with prob. at least1 -δ, J(π ⋆ ) -J( π) ≤ O(1) • σ 2 π ⋆ log(|Π|δ -1 ) n + O(R log(n)) • log(|Π|δ -1 )n .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 a "slow" 1/ √ n-type rate. The slow term in Corollary 3.1 is controlled by the variance σ 2 π ⋆ for the optimal policy. In particular, if π ⋆ is deterministic, then σ 2 π ⋆ = 0, and Corollary 3.1 recovers our bound for the deterministic setting in Corollary 2.1 up to a log(n) factor.To understand the dependence on horizon in Corollary 3.1, we restrict our attention to the "parameter sharing" case where log|Π| = O(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 σ 2 π ⋆ should scale with the horizon. Fortunately, this is not the case: The following result-via a law-of-total-variance-type argument [4] -implies that Corollary 3.1 is fully horizonindependent, with no explicit dependence on horizon when R = O(1) and log|Π| = O(1). For a function f (x 1:H , a 1:H ), let Var π [f ] denote the variance of f under (x 1 , a 1 ), . . . , (x H , a H ) ∼ π . Proposition 3.1. We have that σ2 π ⋆ ≤ Var π ⋆ H h=1 r h ≤ R 2 .For the dense-reward regime where R = H, Proposition 3.1 gives J(π ⋆ ) -J( π) ≲ H log(|Π|)/n. This is somewhat disappointing, as we now require Ω(H 2 ) trajectories (quadratic sample complexity) to learn a non-trivial policy, even when log|Π| = O(1). We show now that this quadratic lower bound is qualitatively tight: the slow H/ √ n rate for σ 2 π ⋆ = H 2 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 σ 2 ∈ H, H 2 , there exists Π with |Π| = 2 such that σ 2 π ⋆ ≤ σ 2 and any (offline or online) IL algorithm must have J(π ⋆ ) -J( π) ≳ σ 2 n with constant probability.Nonetheless, it is possible to obtain linear-in-H sample complexity for dense rewards under a recoverability-like condition. Let us define the signed recoverability constant trajectories suffice to learn an ε-optimal policy. 9See Appendix H for further results concerning tightness of Theorem 3.1, including instance-dependent lower bounds.via µ = max x∈X ,a∈A,h∈[H] (Q π ⋆ h (x, π ⋆ h (x)) -Q π ⋆ h (x, a) . Note that µ ∈ [0, R],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.Proof sketch for Theorem 3.1. When the expert is stochastic, the trajectory-wise distance in Eq. ( 6), is no longer useful (i.e., ρ(π ⋆ ∥ π ⋆ ) ̸ = 0), which necessitates a more information-theoretic analysis. Our starting point is the following scale-sensitive change-of-measure lemma for Hellinger distance.Lemma 3.1 (Change-of-measure for Hellinger distance [34, 35] ). Let P and Q be probability distributions over a measurable space (X , F ). Then for all functions h : X → R,EQUATION)In particular, if h ∈ [0, R] almost surely, then E P [h(X)] ≤ 2 E Q [h(X)] + R • D 2 H (P, Q).We sketch how to use Lemma 3.1 to prove a 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 a trajectory o = (x 1 , a 1 ), . . . ,(x H , a H ) via ∆(o) = H h=1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ).By the performance difference lemma, we can write J(π ⋆ ) -J( π) = E π [∆(o)], so applying Eq. (8) yieldsJ(π ⋆ ) -J( π) = E π [∆(o)] ≲ E π ⋆ [∆(o)] + (E π [∆ 2 (o)] + E π ⋆ [∆ 2 (o)]) • D 2 H (P π , P π ⋆ ).From here, we observe that ), so all that remains is to bound the term E π ∆ 2 (o) . A crude approach is to observe that |∆(o)| ≤ µH, so that applying Lemma 3.E π ⋆ [∆(o)] = 0 and E π ⋆ ∆ 2 (o) = σ 2 π ⋆ (1 gives ≲ E π ⋆ ∆ 2 (o) + ( µH) 2 •D 2 H P π , P π ⋆ , and consequently J(π ⋆ )-J( π) ≲ σ 2 π ⋆ • D 2 H P π , P π ⋆ + µH •D 2 H P π , P π ⋆ .This falls short of Eq. ( 9) due to the suboptimal lower-order term, which does not recover Theorem 2.1 when π ⋆ is deterministic (σ 2 π ⋆ = 0). The full proof in Appendix G.1 corrects this disparity using a subtle and significantly more involved argument based on stopping times and martingale concentration.The following lemma is 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 π, we haveVar π H h=1 r h = E π H h=0 Var π r h + V π h+1 (x h+1 ) | x h ,with the convention that x 0 is a deterministic dummy state (so that P 0 (x 1 = • | x 0 , a = •) is the initial state distribution) and r 0 = 0.Proof of Lemma D.5. Let h ∈ {0, . . . , H} be fixed. We can expandVar π H ℓ=h r ℓ | x h = E π   H ℓ=h r ℓ -V π h (x h ) 2 | x h   = E π   H ℓ=h+1 r ℓ -V π h+1 (x h+1 ) + (r h + V π h+1 (x h+1 ) -V π h (x h )) 2 | x h   = E π   H ℓ=h+1 r ℓ -V π h+1 (x h+1 ) 2 | x h   + E π (r h + V π h+1 (x h+1 ) -V π h (x h )) 2 | x h + 2 E π H ℓ=h+1 r ℓ -V π h+1 (x h+1 ) r h + V π h+1 (x h+1 ) -V π h (x h ) | x h = E π   H ℓ=h+1 r ℓ -V π h+1 (x h+1 ) 2 | x h   + E π (r h + V π h+1 (x h+1 ) -V π h (x h )) 2 | x h = E π Var π H ℓ=h+1 r ℓ | x h+1 | x h + Var π (r h + V π h+1 (x h+1 ) | x h .We conclude inductively that for all h ∈ {0, . . . , H},Var π H ℓ=h r ℓ | x h = H ℓ=h E π Var π (r ℓ + V π ℓ+1 (x ℓ+1 ) | x ℓ | x h .To obtain the final expression, we note thatVar π H h=1 r h = Var π H h=0 r h | x 0 ,under the convention that x 0 is a deterministic dummy state (so that P 1 (x 1 = • | x 0 , a) is the initial state distribution) and r 0 = 0.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 a setting where we receive {z i } n i=1 i.i.d. from z ∼ g ⋆ , where g ⋆ ∈ ∆(Z). We have a class G ⊆ ∆(Z) that may or may not contain g ⋆ . We analyze the following maximum likelihood estimator:EQUATIONTo provide sample complexity guarantees that support infinite classes, we 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 a class G ⊂ ∆(Z), we set that a class G ′ ⊂ ∆(Z) is an ε-cover if for all g ∈ G, there exists g ′ ∈ G ′ such that for all z ∈ Z, log(g(z)/g ′ (z)) ≤ ε. We denote the size of the smallest such cover by N log (G, ε).We also allow for optimization errors, and concretely assume that g satisfiesn i=1 log( g(z i )) ≥ max g∈G n i=1 log(g(z i )) -ε opt • nfor a parameter ε opt ≥ 0; the case ε opt = 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 least1 -δ, D 2 H ( g, g ⋆ ) ≤ inf ε>0 6 log(2N log (G, ε)/δ -1 ) n + 4ε + 2 inf g∈G log(1 + D χ 2 (g ⋆ ∥ g)) + 2ε opt .In particular, if G is finite, the maximum likelihood estimator satisfiesD 2 H ( g, g ⋆ ) ≤ 6 log(2|G|/δ -1 ) n + 2 inf g∈G log(1 + D χ 2 (g ⋆ ∥ g)) + 2ε opt .Note that the term inf g∈G log(1 + D χ 2 (g ⋆ ∥ g)) corresponds to misspecification error, and is zero ifg ⋆ ∈ G.Proof of Proposition D.1. Let G ε denote a minimal ε-cover for G, and let g ∈ G ε denote any element that covers g in the sense of Definition D.1. Going forward, we will use that g satisfiesEQUATIONLet ℓ i (g) =log(g(z i )), and setL(g) = - n i=1 log(g(z i )). Set X i (g) = 1 2 (ℓ i (g) -ℓ i (g ⋆ )). By applying Lemma D.1 with the sequence (X i (g)) n i=1 for each g ∈ G ε and taking a union bound, we have that with probability at least1 -δ, for all g ∈ G ε -n • log E z∼g ⋆ e 1 2 log(g(z)/g ⋆ (z)) ≤ 1 2 L(g) -L(g ⋆ ) + log(|G ε |δ -1 ).Using a standard argument [102] , we have that-log E z∼g ⋆ e 1 2 log(g(z)/g ⋆ (z)) = -log 1 - 1 2 D 2 H (g, g ⋆ ) ≥ 1 2 D 2 H (g, g ⋆ ).In particular, this implies thatD 2 H ( g, g ⋆ ) ≤ 2 log(|G|/δ -1 ) n + 1 n L( g) -L(g ⋆ ) ,and soD 2 H ( g, g ⋆ ) ≤ 2D 2 H ( g, g) + 2D 2 H ( g, g ⋆ ) ≤ 4 log(|G|/δ -1 ) n + 2 n L( g) -L(g ⋆ ) + 2ε,by the triangle inequality for Hellinger distance and Eq. (11) .It remains to bound the right-hand-side. Let g ∈ G be arbitrary. We can boundEQUATION) by the definition of the maximum likelihood estimator. For the first term in Eq. ( 12), we observe thatL( g) -L(g ⋆ ) = n i=1 log(g ⋆ (z i )/ g(z i )) ≤ εn, by Definition D.1.To bound the second term in Eq. ( 12), set Y i = -(ℓ t (g)ℓ t (g ⋆ )). Applying Lemma D.1 with the sequence (Y i ) n i=1 , we have that with probability at least1 -δ, L(g) -L(g ⋆ ) ≤ n • log E z∼g ⋆ e log(g ⋆ (z)/g(z)) + log(δ -1 ).Finally, note thatlog E z∼g ⋆ e log(g ⋆ (z)/g(z)) = log E z∼g ⋆ g ⋆ (z) g(z) = log(1 + D χ 2 (g ⋆ ∥ g)).The result follows by choosing g ∈ G to minimize this quantity.Part IThis 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.In this section, we give bounds on the generalization error D 2 H P π , P π ⋆ for log-loss behavior cloning for concrete classes Π of interest. To do so, we observe that the log-loss behavior cloning objectiveπ = arg max π∈Π n i=1 H h=1 log(π h (a i h | x i h )).is equivalent to performing maximum likelihood estimation over the density class P = {P π } π∈Π . Indeed, for any π ∈ Π, we haven i=1 log(P π (o i )) = n i=1 log P 0 (x i 1 ) H h=1 P h (x i h+1 | x i h , a i h )π h (a i h | x i h ) = n i=1 H h=1 log(π h (a i h | x i h )) + C(D),where C(D) is a constant that depends on the dataset D but not on π. 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 MLE given in Appendix D.4.To give guarantees that support infinite policy classes, we appeal to the following notion of covering number.Definition E.1 (Policy covering number). For a class Π ⊂ {π h : X → ∆(A)}, we set that Π ′ ⊂ {π h : X → ∆(A)} is an ε-cover if for all π ∈ Π, there exists π ′ ∈ Π ′ such that for all x ∈ X , a ∈ A, and h ∈[H], log(π h (a | x)/π ′ h (a | x)) ≤ ε.We denote the size of the smallest such cover by N pol (Π, ε).In addition, to allow for optimization errors, we replace Eq. ( 4) with the assumption that π satisfiesEQUATION)for a parameter ε opt > 0; Eq. ( 4) is the special case in which ε opt = 0. With these definitions, specializing Proposition D.1 leads to the following result.Theorem E.1 (Generalization bound for LogLossBC). The LogLossBC policy in Eq. ( 13) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ inf ε>0 6 log(2N pol (Π, ε/H)δ -1 ) n + 4ε + 2 inf π∈Π log 1 + D χ 2 P π ⋆ ∥ P π + 2ε opt .In particular, if Π is finite, the log-loss behavior cloning policy satisfiesD 2 H P π , P π ⋆ ≤ 6 log(2|Π|δ -1 ) n + 2 inf π∈Π log 1 + D χ 2 P π ⋆ ∥ P π + 2ε opt .Let us make two remarks.• First, the only explicit dependence on the horizon H is through the precision ε/H through which we evaluate the covering number: N pol (Π, ε/H). As a result, for parametric classes where N pol (Π, ε) ≍ log(ε -1 ) (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 π∈Π log(1 + D χ 2 P π ⋆ ∥ P π ) corresponds to misspecification error, and is zero if π ⋆ ∈ Π. We remark that when π ⋆ is deterministic, this expression can be simplified toinf π∈Π log E π ⋆ 1 H h=1 π h (a h |x h ).Proof of Theorem E.1. This follows by applying Proposition D.1 with the class {P π } π∈Π , and noting that if π ′ covers π in the sense of Definition E.1, then for all o ∈ (X × A) H , we have log(P π (o)/P π ′ (o)) ≤ εH, meaning that an ε-cover in the sense of Definition E.1 yields an εH-cover in the sense of Definition D.1.We now instantiate Theorem E.1 to give generalization bounds for specific policy classes of interest.Consider a tabular MDP in which |X |, |A| < ∞ are small and finite. Here, choosing Π to be the set of all stationary policies leads to a bound independent of H.When Π is the set of all deterministic stationary policies, the log-loss behavior cloning policy Eq. ( 4) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ O |X | log(|A|δ -1 ) n .Meanwhile, if Π is the set of all stochastic stationary policies, the log-loss behavior cloning policy Eq. ( 4) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ O |X ||A| log(Hnδ -1 ) n .Proof of Corollary E.1. This follows by noting that we have log|Π| ≤ |X | log|A| in the deterministic case and log N pol (Π, ε) ≤ O |X ||A| log(ε -1 ) in the stochastic case (this follows 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 Π is the set of all deterministic non-stationary policies, the log-loss behavior cloning policy Eq. ( 4) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ O H|X | log(|A|δ -1 ) n .Meanwhile, if Π is the set of all stochastic non-stationary policies, the log-loss behavior cloning policy Eq. ( 4) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ O H|X ||A| log(Hnδ -1 ) n .Proof of Corollary E.2. This follows because we have log|Π| ≤ H|X | log|A| in the deterministic case and log N pol (Π, ε) ≤ O H|X ||A| log(ε -1 ) in the stochastic case.Next, we give an example of a general family of policy classes based on function approximation for which the sample complexity is at most polylogarithmic in H.For a vector v ∈ R A , let σ : R A → ∆(A) be the softmax function, which is given byσ a (v) = exp(v a ) a ′ ∈A exp(v a ′ ) . Let F ⊂ {f h : X × A → R} H h=1be a class of value functions, and define the induced class of softmax policies viaΠ F = {π f | f ∈ F}, where π f,h (x) := σ a (f h (x, a)).We give sample complexity guarantees based on covering numbers for the value function class F.For a class F ⊂ {f h : X × A → R}, we set thatF ′ ⊂ {f h : X × A → R} is an ε-cover if for all f ∈ F, there exists f ′ ∈ F ′ such that for all x ∈ X , a ∈ A, and h ∈ [H], |f h (x, a) -f ′ h (x, a)| ≤ ε.We denote the size of the smallest such cover by N val (Π, ε).. When Π = Π F 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δ,D 2 H P π , P π ⋆ ≤ O(1) • inf ε>0 log(N val (F, ε/H)δ -1 ) n + ε + 2 inf π∈Π F log 1 + D χ 2 P π ⋆ ∥ P π . Proof of Corollary E.3. Consider a pair of functions f, f ′ with |f h (x, a) -f ′ h (x, a)| ≤ ε for all x ∈ X , a ∈ A, and h ∈ [H]. The induced softmax policies satisfy log(π f,h (a | x)/π f ′ ,h (a | x)) = f h (x, a) -f ′ h (x, a) + log a ′ ∈A exp(f ′ h (x, a ′ )) a∈A exp(f ′ h (x, a ′ )).Clearly we have f h (x, a)f ′ h (x, a) ≤ ε, and we can boundlog a ′ ∈A exp(f ′ h (x, a ′ )) a∈A exp(f h (x, a ′ )) = log a ′ ∈A exp(f h (x, a ′ )) • exp(f ′ h (x, a ′ ) -f h (x, a ′ )) a∈A exp(f h (x, a ′ )) ≤ log a ′ ∈A exp(f h (x, a ′ )) • max a ′′ ∈A exp(f ′ h (x, a ′′ ) -f h (x, a ′′ )) a∈A exp(f h (x, a ′ )) ≤ max a ′′ ∈A {f ′ h (x, a ′′ ) -f h (x, a ′′ )} ≤ ε.Hence, an ε-cover in the sense of Definition E.2 implies a 2ε-cover in the sense of Definition E.1.Whenever F is parametric in the sense that log N val (F, ε) ∝ log(ε -1 ), Corollary E.3 leads to polylogarithmic dependence on H. The following result gives such an example.Linear softmax policies. Consider the set of stationary linear softmax policies induced by the value function classF = {(x, a, h) → ⟨ϕ h (x, a), θ⟩ | ∥θ∥ 2 ≤ B},where ϕ h (x, a) ∈ R d is a known feature map with ∥ϕ h (x, a)∥ ≤ B. Here, we have log N val (F, ε) ∝ d log(Bε -1 ) (e.g., Wainwright [91] ), which yields the following generalization guarantee.Corollary E.4. When Π is the set of stationary linear softmax policies and π ⋆ ∈ Π, the log-loss behavior cloning policy Eq. ( 4) has that with probability at least 1δ,D 2 H P π , P π ⋆ ≤ O d log(BHnδ -1 )n .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 is 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 IL. For this comparison, we are be mainly interested in the case of deterministic expert policies, but our 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 in which the learner can directly interact with the underlying MDP M ⋆ and query the expert advice. Concretely, for each episode i ∈ [n], the learner executes a policyπ i = {π i h : X → ∆(A)} H h=1 and receives a trajectory o t = (x i 1 , a i 1 , a ⋆,i 1 ), . . . , (x i H , a i H , a ⋆,i H ), in which a i h ∼ π i h (x i h ), a ⋆,i h ∼ π ⋆ (x t h), and x i h+1 ∼ P h (x i h , a i h ); in other words, the trajectory induced by the learner's policy is annotated by the expert's action a ⋆ h ∼ π ⋆ h (x h ) at each state x h encountered. After all n episodes conclude, they can use all of the data collected to produce a policy π such that J(π ⋆ ) -J( π) is small. Dagger algorithm. We consider a general version of the Dagger algorithm. The algorithm is parameterized by an online learning algorithm Alg Est , which attempts to estimate the expert policy in a sequential fashion based on trajectories.Set D 1 = ∅. For i = 1, . . . , n:• Query online learning algorithm Alg Est with D i and receive policy π.i = (x i 1 , a i 1 , a ⋆,i 1 ), . . . , (x i H , a i H , a ⋆,i H ). • Update D i+1 ← D i ∪ {o i }.At the end, we output π = unif(π 1 , . . . , π n ) as the final policy.To measure the performance of the estimation oracle, we define the online estimation error as:Est on H (n) = 1 n n i=1 H h=1 E π i D 2 H ( π i h (x h ), π ⋆ (x h )) .As we will show in a moment, this notion of estimation error is well-suited for online learning algorithms that estimate π ⋆ using the logarithmic loss.Our following result gives a general guarantee for Dagger that holds for any choice of online learning algorithm. To state the result, let P π ⋆ |π denote the law of o = (x 1 , a 1 , a ⋆ 1 ), . . . , (x H , a H , a ⋆ H ) when π ⋆ is the expert policy and we execute π. Letσ 2 π ⋆ |π = H h=1 E π• h π ⋆ (Q π ⋆ h (x h , a h ) -V π ⋆ h (x h )) 2 , so that σ 2 π ⋆ = σ 2 π ⋆ |π ⋆ and define σ 2 π ⋆ = sup π σ 2 π ⋆ |π . Note that σ 2 π ⋆ = 0 whenever π ⋆ is deterministic, but in general, σ 2 π ⋆ ≥ σ 2 π ⋆ . Proposition E.1 (Regret for Dagger).For any MDP M ⋆ with signed recoverability parameter µ and any online learning algorithm Alg Est , Dagger ensures thatEQUATIONTo instantiate the bound above, we choose Alg Est by applying the exponential weights algorithm (e.g., Cesa-Bianchi and Lugosi [19] ) with the logarithmic loss. Let Π h := {π h | π ∈ Π} denote the projection of Π onto step h. The algorithm proceeds as follows. At step i ∈ [n], given the dataset D i , for each layer h ∈ [H] we define a distributionµ i h ∈ ∆(Π h ) via µ i h (π) ∝ exp   j<j log(π h (a ⋆,j h | x j h ))   = j<j π h (a ⋆,j h | x j h ).We then setπ i h (a | x) = E π h ∼µ i h [π h (a | x)].We refer to the resulting algorithm as LogLossDagger. This leads to the following guarantee for finite classes.Proposition E.2 (Regret for LogLossDagger). When π ⋆ ∈ Π, the log-loss exponential weights algorithm ensures that with probability at least 1δ,Est on H (n) ≤ 2 n H h=1 log(|Π h |Hδ -1 ).Consequently, LogLossDagger ensures that with probability at least 1δ,J(π ⋆ ) -J( π) ≲ σ 2 π ⋆ • H h=1 log(|Π h |Hδ -1 ) n + µ • H h=1 log(|Π h |Hδ -1 ) n ,and when π ⋆ is deterministic,J(π ⋆ ) -J( π) ≲ µ • H h=1 log(|Π h |Hδ -1 ) n .We note that for many parameter regimes, the sample complexity bound in Proposition E.1 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-like quantity in the leading order term is weaker). It 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 writingJ(π ⋆ ) -J( π) = H h=1 E π| π Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) .Fix a layer h. By Lemma 3.1, we haveE π| π Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) ≤ E π ⋆ | π Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) + E π| π [(Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ] + E π ⋆ | π [(Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ] E π [D 2 H ( π h (x h ), π ⋆ h (x h ))] = E π| π [(Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ] + E π ⋆ | π [(Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ] E π [D 2 H ( π h (x h ), π ⋆ h (x h ))].Furthermore, using Lemma 3.1, we haveE π| π (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ≲ H h=1 E π ⋆ | π (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 + µ 2 H h=1 E π D 2 H ( π h (x h ), π ⋆ h (x h )) ,so thatEQUATION≲ E π ⋆ | π [(Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 ] • E π [D 2 H ( π h (x h ), π ⋆ h (x h ))] + µ • E π D 2 H ( π h (x h ), π ⋆ h (x h )) .Recall that the Dagger policy satisfiesJ(π ⋆ ) -J( π) = 1 n n i=1 J(π ⋆ ) -J( π i ).Applying Eq. ( 15) to each policy π i , summing over all layer h, and applying Cauchy-Schwarz yieldsJ(π ⋆ ) -J( π) ≲ 1 n n i=1 σ 2 π ⋆ |π i • Est on H (n) + µ • Est on H (n) ≲ σ 2 π ⋆ • Est on H (n) + µ • Est on H (n).In the deterministic case, we tighten the argument above by applying the following improved changeof-measure argument based on Lemma 3.1:E π ⋆ | π Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) ≤ E π ⋆ | π (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) + ≤ 2 E π ⋆ | π (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) + + µ • E π D 2 H ( π h (x h ), π ⋆ h (x h )) = µ • E π D 2 H ( π h (x h ), π ⋆ h (x h )) ,This leads to Eq. ( 14).Proof of Proposition E.2. Since π ⋆ ∈ Π, a standard guarantee for exponential weights with the log-loss (e.g., Cesa-Bianchi and Lugosi [19] ) ensures that for all h ∈ [H], the following bound holds almost surely:n i=1 log(1/ π i h (a ⋆,i h | x i h )) ≤ n i=1 log(1/π ⋆ h (a ⋆,i h | x i h )) + log|Π h |.From here, for each h ∈ [H], Lemma A.14 of Foster et al. [34] implies that with probability at least 1δ,n i=1 E π i D 2 H ( π i h (x h ), π ⋆ (x h )) ≤ log|Π h | + 2 log(δ -1 ).The result now follows by taking a union bound.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 π ′ , defineρ(π ∥ π ′ ) := E π E a ′ 1:H ∼π ′ (x 1:H ) [I{∃h : a h ̸ = a ′ h }],where we use the shorthanda ′ 1:H ∼ π ′ (x 1:H ) to indicate that a ′ 1 ∼ π ′ 1 (x 1 ), . . . , a ′ H ∼ π ′ H (x H). Despite being defined in an asymmetric fashion, the following lemma shows that the trajectory-wise distance ρ(• ∥ •) is symmetric, from which it follows that it is indeed a semi-metric.Lemma F.1. For all (potentially stochastic) policies π and π ′ , it holds thatρ(π ∥ π ′ ) = ρ(π ′ ∥ π).Next, we show that it is possible to bound the difference in reward for any pair of policies in terms of the trajectory-wise distance ρ(• ∥ •).Lemma F.2. For all (potentially stochastic) policies π and π ′ , it holds thatJ(π) -J(π ′ ) ≤ R • ρ(π ∥ π ′ ).Finally, using Lemma F.1, 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 π ⋆ be a deterministic policy and π be an arbitrary stochastic policy. Then we have that1 4 • ρ(π ⋆ ∥ π) ≤ D 2 H P π , P π ⋆ ≤ 2 • ρ(π ⋆ ∥ π).Combining Lemmas F.2 and F.3, we conclude that for any deterministic policy π ⋆ and stochastic policy π,J(π ⋆ ) -J( π) ≤ 4R • D 2 H P π , P π ⋆ .Proof of Lemma F.1. This follows by noting that we can writeρ(π ∥ π ′ ) = 1 -E π E a ′ 1:H ∼π ′ (x 1:H ) [I{a h = a ′ h ∀h}] = 1 - x 1:H ,a 1:H ,a ′ 1:H P 0 (x 1 ) H h=1 P h (x h+1 | x h , a h )π h (a h | x h )π ′ h (a ′ h | x h )I{a h = a ′ h } = 1 - x 1:H ,a 1:H ,a ′ 1:H P 0 (x 1 ) H h=1 P h (x h+1 | x h , a ′ h )π h (a h | x h )π ′ h (a ′ h | x h )I{a h = a ′ h } = 1 -E π ′ E a ′ 1:H ∼π(x 1:H ) [I{a h = a ′ h ∀h}] = ρ(π ′ ∥ π).Proof of Lemma F.2. Observe that sinceH h=1 r h ∈ [0, R],we can bound the reward for π asJ(π) ≤ E π H h=1 r h E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] + R • E π E a ′ 1:H ∼π ′ (x 1:H ) [I{∃h : a ′ h ̸ = a h }] = E π H h=1 r h E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] + R • ρ(π ∥ π ′ ).We can bound the first term asE π H h=1 r h E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] = E π f (x 1:H , a 1:H ) E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] ,where f (x 1:H , a 1:H ) := H h=1 E[r h | x h , a h ].We now observe that for any function f ,E π f (x 1:H , a 1:H ) E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] = x 1:H ,a 1:H ,a ′ 1:H f (x 1:H , a 1:H ) • P 0 (x 1 ) H h=1 P h (x h+1 | x h , a h )π h (a h | x h )π ′ h (a ′ h | x h )I{a h = a ′ h } = x 1:H ,a 1:H ,a ′ 1:H f (x 1:H , a ′ 1:H ) • P 0 (x 1 ) H h=1 P h (x h+1 | x h , a ′ h )π h (a h | x h )π ′ h (a ′ h | x h )I{a h = a ′ h } ≤ x 1:H ,a ′ 1:H f (x 1:H , a ′ 1:H ) • P 0 (x 1 ) H h=1 P h (x h+1 | x h , a ′ h )π ′ h (a ′ h | x h ) = E π ′ [f (x 1:H , a 1:H )]. We conclude that E π H h=1 r h E a ′ 1:H ∼π ′ (x 1:H ) [I{a ′ h = a h ∀h}] ≤ J(π ′ ), so that J(π) -J(π ′ ) ≤ R • ρ(π ∥ π ′ ).Proof of Lemma F.3. Define the triangular discrimination via D ∆ (P, Q) := (dP-dQ) 2 dP+dQ , and recall that 1 2 D ∆ (P, Q) ≤ D 2 H (P, Q) ≤ D ∆ (P, Q) (e.g., Foster and Krishnamurthy [32] ). Next, define the shorthand P (x 1:H | a 1:H ) := H-1 h=0 P (x h+1 | x h , a h ) and P π (a 1:H | x 1:H ) := H h=1 π h (a h | x h ) (these quantities do not have an interpretation as conditional probability measures in the way the notation might suggest, but this will not be relevant to the proof). For any deterministic policy π ⋆ , we can writeD ∆ P π , P π ⋆ = x 1:H a 1:H P (x 1:H | a 1:H-1 ) • (P π (a 1:H | x 1:H ) -P π ⋆ (a 1:H | x 1:H )) 2 P π (a 1:H | x 1:H ) + P π ⋆ (a 1:H | x 1:H ) = x 1:H a 1:H =π ⋆ (x 1:H ) P (x 1:H | a 1:H-1 ) • (P π (a 1:H | x 1:H ) -P π ⋆ (a 1:H | x 1:H )) 2 P π (a 1:H | x 1:H ) + P π ⋆ (a 1:H | x 1:H ) + x 1:H a 1:H ̸ =π ⋆ (x 1:H ) P (x 1:H | a 1:H-1 ) • (P π (a 1:H | x 1:H ) -P π ⋆ (a 1:H | x 1:H )) 2 P π (a 1:H | x 1:H ) + P π ⋆ (a 1:H | x 1:H ) . Since π ⋆ is deterministic, P π ⋆ (a 1:H | x 1:H ) = 1 if a 1:H = π ⋆ (x 1:H ),and is P π ⋆ (a 1:H | x 1:H ) = 0 otherwise. Using this, we can write the second term above asx 1:H a 1:H ̸ =π ⋆ (x 1:H ) P (x 1:H | a 1:H-1 ) • (P π (a 1:H | x 1:H ) -0) 2 P π (a 1:H | x 1:H ) + 0 = x 1:H a 1:H ̸ =π ⋆ (x 1:H ) P (x 1:H | a 1:H-1 )P π (a 1:H | x 1:H ) = P π [∃h : a h ̸ = π ⋆ (x H )] = ρ(π ∥ π ⋆ ).This proves that D ∆ P π , P π ⋆ ≥ ρ(π ∥ π ⋆ ). For the upper bound, we use that π ⋆ is deterministic once more to write the first term above asx 1:H a 1:H =π ⋆ (x 1:H ) P (x 1:H | a 1:H-1 ) • (P π (a 1:H | x 1:H ) -1) 2 P π (a 1:H | x 1:H ) + 1 = E π ⋆ (P π (a 1:H | x 1:H ) -1) 2 P π (a 1:H | x 1:H ) + 1 ≤ E π ⋆ (P π (a 1:H | x 1:H ) -1) 2 .We further note thatE π ⋆ (P π (a 1:H | x 1:H ) -1) 2 = E π ⋆ E a ′ 1:H ∼π(x 1:H ) [1 + (P π (a ′ 1:H | x 1:H ) -2)I{a ′ 1:H = a 1:H }] ≤ E π ⋆ E a ′ 1:H ∼π(x 1:H ) [1 -I{a ′ 1:H = a 1:H }] = E π ⋆ E a ′ 1:H ∼π(x 1:H ) [I{∃h : a ′ 1:H ̸ = a 1:H }] = ρ(π ⋆ ∥ π). By Lemma F.1, we conclude that D ∆ P π , P π ⋆ ≤ ρ(π ∥ π ⋆ ) + ρ(π ⋆ ∥ π) = 2ρ(π ⋆ ∥ π). F.2 Proof of Theorem 2.2 Proof of Theorem 2.2.For this proof, we consider a slightly more general online imitation learning model in which the learner is allowed to select a i h based on the sequence(x i 1 , a i 1 , a ⋆,i 1 ), . . . , (x i h-1 , a i h-1 , a ⋆,i h-1), (x i h , a ⋆,i h ) at training time; this subsumes the offline imitation learning model. Let n ∈ N and H ∈ N be fixed. Let ∆ ∈ (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 Π. Set X = {x, y} and A = {a, b}. The initial state distribution sets P 0 (x) = 1 -∆ and P 0 (y) = ∆. The transition dynamics are P h (x ′ | x, a) = I{x ′ = x} for all h; that is, x, y are self-looping terminal states. We set Π = {π a , π b }, where the expert policies are π a , which sets π a h (x) = a for all h and x, and π b , which sets π b h (x) = a and sets π b h (y) = b. Let a problem instance I = (M ⋆ , r, π ⋆ ) refer to a tuple consisting of the reward-free MDP M ⋆ , a reward function r = {r h } H h=1 , and an expert policy π ⋆ . We consider two problem instances, I a = (M ⋆ , r a , π a ) and I b = (M ⋆ , r b , π b ):• For problem instance I a , the expert policy is π a . We set r a h (x, •) = 0, r a h (y, a) = I{a = a} for all h.• For problem instance I b , the expert policy is π b . We set r b h (x, •) = 0, r b h (y, a) = I{a = b} for all h.Note that both of these instances satisfy µ = 1, and that π a and π b are optimal policies for their respective instances. Let J a denote the expected reward function for instance I a , and likewise for I b .Going forward, we fix the online imitation learning algorithm under consideration and let P a denote the law of o 1 , . . . , o n when we execute the algorithm on instance a, and likewise for b; let E a [•] and E b [•] denote the corresponding expectations. In addition, for any policy π, let P π a |π denote the law of o = (x 1 , a 1 , a ⋆ 1 ), . . . , (x H , a H , a ⋆ H ) when we execute π in the online imitation learning framework and the expert policy is π ⋆ = π a , and define P π b |π analogously.We first observe that for any policy π,J a (π a ) -J a ( π) = ∆ • H h=1 E a h ∼ π h (y) [I{a h ̸ = π a h (y)}],and thatJ b (π b ) -J b ( π) = ∆ • H h=1 E a h ∼ π h (y) [I{a h ̸ = π b h (y)}]. Defining ρ(π, π ′ ) = H h=1 E a h ∼π h (y),a ′ h ∼π ′ h (y) I{a h ̸ = a ′h } as a metric, we note that ρ(π a , π b ) = H, and hence by the standard Le Cam two-point argument (e.g.,. Wainwright [91] ), the algorithm must havemax{E a [J a (π a ) -J a ( π)], E b [J b (π b ) -J b ( π)]} ≥ ∆H 4 (1 -D TV (P a , P b )),where D TV (•, •) denotes total variation distance. Next, using Lemma D.2 of Foster et al. [36] , we can boundD 2 TV (P a , P b ) ≤ D 2 H (P a , P b ) ≤ 7 E a n i=1 D 2 H P π a |π i , P π b |π i .Since, the feedback the learner receives for a given episode i is identical under instances I a and I b unless x 1 = y (regardless of how π i is chosen), we can boundD 2 H P π a |π i , P π b |π i ≤ 2∆,and henceD 2TV (P a , P b ) ≤ 14∆n. We set ∆ = 1/56n, and conclude that any algorithm must havemax{E a [J a (π a ) -J a ( π)], E b [J b (π b ) -J b ( π)]} ≥ ∆H 8 = c • H n for an absolute constant c > 0.G Proofs from Section 3 G.1 Proof of Theorem 3.1 Proof of Theorem 3.1. Assume without loss of generality that R = 1. Let o = (x 1 , a 1 ), . . . , (x H , a H ), and for each h ∈ [H], define the sum of advantages up to step h via∆ h (o) = h ℓ=1 Q π ⋆ ℓ (x ℓ , π ⋆ ℓ (x ℓ )) -Q π ⋆ ℓ (x ℓ , a ℓ ) ,which has |∆(o)| ≤ H almost surely. Consider the filtration F h := σ(x 1 , a 1 , . . . , x h , a h ). Fix a parameter L ≥ 1 whose value will be chosen later, and define a random variableH ⋆ := min{h | |∆ h (o)| > L},with H ⋆ := H + 1 if there is no h such that |∆ h (o)| > L; we will adopt the convention thatQ π ⋆ H+1 = V π ⋆ H+1 = 0. Lemma G.1. H ⋆ is a stopping time with respect (F h ) h≥1 , 17 and has |∆ H ⋆ (o)| ≤ L + 1 almost surely.The following lemma, which is one of the central technical components of this proof, gives a 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 ∆ H ⋆ bounded, which facilitates a strong change-of-measure argument in the sequel.H h=1 r h ∈ [0, R],then for all policies π, we have thatEQUATION)Note that even though we assume R = 1 throughout this proof, we state this lemma for general R for the sake of keeping it self-contained.We proceed to bound the right-hand-side of Eq. ( 16) using change-of-measure based on Hellinger distance (Lemma 3.1). For the second term in Eq. ( 16), Lemma 3.1 givesP π [H ⋆ ≤ H] ≤ 2P π ⋆ [H ⋆ ≤ H] + D 2 H P π , P π ⋆ = 2P π ⋆ [∃h : |∆ h (o)| > L] + D 2 H P π , P π ⋆ .For the first term in Eq. ( 16), Lemma 3.1, gives thatE π [∆ H ⋆ (o)] ≤ E π ⋆ [∆ H ⋆ (o)] + 1 2 E π [∆ 2 H ⋆ (o)] + E π ⋆ [∆ 2 H ⋆ (o)] • D 2 H (P π , P π ⋆ ).To bound the first moment and second moment of ∆ H ⋆ (o) under π ⋆ , we use the following lemma, which follows from elementary properties of stopped martingale difference sequences.Lemma G.3. We have thatE π ⋆ [∆ H ⋆ (o)] ≤ 0, and E π ⋆ ∆ 2 H ⋆ (o) ≤ 4σ 2 π ⋆ .It remains to bound the second moment under π. Here, since |∆ H ⋆ (o)| ≤ L + 1 almost surely by Lemma G.1, we note that Lemma 3.1 givesE π ∆ 2 H ⋆ (o) ≤ 2 E π ⋆ ∆ 2 H ⋆ (o) + (L + 1) 2 D 2 H P π , P π ⋆ .Combining these developments, we have thatE π [∆ H ⋆ (o)] ≤ 3 2 E π ⋆ [∆ 2 H ⋆ (o)] • D 2 H (P π , P π ⋆ ) + (L + 1)D 2 H P π , P π ⋆ ≤ 6σ 2 π ⋆ • D 2 H (P π , P π ⋆ ) + (L + 1)D 2 H P π , P π ⋆ ,and thusJ(π ⋆ ) -J( π) ≤ 6σ 2 π ⋆ • D 2 H (P π , P π ⋆ ) + (L + 2)D 2 H P π , P π ⋆ + 2P π ⋆ [∃h : |∆ h (o)| > L].To wrap up, we appeal to the second of our main technical lemmas, Lemma G.4.Lemma G.4 (Concentration for advantages). Assume that r h ≥ 0 and H h=1 r h ∈ [0, R] almost surely for some R > 0. Then for any (potentially stochastic) policy π, it holds that for all δ ∈ (0, e -1 ),P π   ∃H ′ : H ′ h=1 Q π h (x h , a h ) -V π h (x h ) ≥ c • R log(δ -1 )   ≤ δ,for an absolute constant c > 0.Let ε ∈ (0, e -1 ) be fixed. If we defineL = c • log(ε -1 ),where c > 1 is a sufficiently large absolute constant, then by Lemma G.4, we have thatP π ⋆ [∃h : |∆ h (o)| > L] ≤ ε.This proves the result.Proof of Lemma G.1. To prove that H ⋆ is a stopping time, we observe that for all h ≤ H, we haveI{h = H ⋆ } = I{|∆ h (o)| > L, |∆ h ′ (o)| ≤ L ∀h ′ < h},and ∆ h (o) is a measurable function of (x 1 , a 1 ), . . . , (x h , a h ). Likewise, we haveI{h = H ⋆ + 1} = I{|∆ h (o)| ≤ L ∀h ≤ H},which is a measurable function of (x 1 , a 1 ), . . . , (x H , a H ).For the second claim, we observe that|∆ H ⋆ (o)| ≤ |∆ H ⋆ -1 (o)| + Q π ⋆ H ⋆ (x H ⋆ , π ⋆ H ⋆ (x H ⋆ )) -Q π ⋆ H ⋆ (x H ⋆ , a H ⋆ ) ≤ L + 1 almost surely. Proof of Lemma G.3. Define X h := Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h), and F h = σ(x 1 , a 1 , . . . , x h , a h ), with X H+1 := 0. Since H ⋆ is a stopping time with respect to (F h ) and X h is a martingale difference sequence (under π ⋆ ), the optional stopping theorem (e.g., [96] ) implies that 18E π ⋆ [∆ H ⋆ (o)] = E π ⋆ H ⋆ h=1 X h = 0.We now bound the second moment. Recall Doob's maximal inequality (e.g., Williams [96] ).Lemma G.5.If (S h ) h∈[H] is a non-negative submartingale, then E max h∈[H] S 2 h ≤ 4 E S 2 H .We claim that |∆ h (o)| is a submartingale, since a convex function of a martingale is a submartingale. 19 As a result, Lemma G.5 gives thatE ∆ 2 H ⋆ (o) ≤ E max h∈[H] ∆ 2 h (o) ≤ 4 E ∆ 2 H (o) .Finally, we note thatE π ⋆ ∆ 2 H (o) = E π ⋆   H h=1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) 2   = H h=1 E π ⋆ (Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h )) 2 = σ 2 π ⋆ ,where we have once more used thatX h = Q π ⋆ h (x h , π ⋆ h (x h ))-Q π ⋆ h (x h , a h) is a martingale difference sequence.Proof of Lemma G.2. Consider the following non-Markovian policy:π h (• | x 1:h , a 1:h-1 ) = π h (• | x h ) h ≤ H ⋆ , π ⋆ h (• | x h ) h > H ⋆. This is a well-defined policy, since we can write I{h > H ⋆ } = max h ′ <h I{h ′ = H ⋆ }, andI{h ′ = H ⋆ } is a measurable function of (x 1 , a 1 ), . . . , (x h ′ , a h ′ ) ⊂ (x 1 , a 1 ), . . . , (x h-1 , a h-1 ) for h ′ < h.We begin by writingEQUATIONFor the second pair of terms in Eq. ( 17), we use the following lemma.Lemma G.6. Under the same assumptions as Lemma G.2, it holds thatJ( π) -J( π) ≤ R • P π [H ⋆ ≤ H].18 To give self-contained proof, note that we can writeE π ⋆ H ⋆ h=1 X h = E π ⋆ H h=1 X h I{H ⋆ ≥ h} We claim that I{H ⋆ ≥ h} is a measurable function of F h-1 , since I{H ⋆ ≥ h} = 1 -I{H ⋆ < h}, and I{H ⋆ = h ′ } is a measurable function of (x1, a1), . . . , (x h ′ , a h ′ ) ⊂ (x1, a1), . . . , (x h-1 , a h-1 ) for h ′ < h. We conclude that E π ⋆ [X h I{H ⋆ ≥ h} | F h-1 ] = E π ⋆ [X h | F h-1 ]I{H ⋆ ≥ h} = 0. 19 For completeness, note that E[|∆ h (o)| | F h-1 ] = E[|∆ h-1 (o) + X h | | F h-1 ] ≥ |∆ h-1 (o) + E[X h | F h-1 ]| = |∆ h-1 (o)|.For the first pair of terms in Eq. ( 17), using the performance difference lemma, we can write20 J(π ⋆ ) -J( π) = E π H h=1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) = E π H h=1 E h-1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) = E π H h=1 E h-1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) I{h ≤ H ⋆ } = E π H h=1 E h-1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) I{h ≤ H ⋆ } = E π H ⋆ h=1 Q π ⋆ h (x h , π ⋆ h (x h )) -Q π ⋆ h (x h , a h ) = E π [∆ H ⋆ (o)],where the third equality uses thatπ h (• | x 1:h , a 1:h-1 ) = π ⋆ h (• | x h ) for h > H ⋆, and the fourth equality uses that I{h ≤ H ⋆ } is F h-1 -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 thatE π [∆ H ⋆ (o)] = E π [∆ H ⋆ (o)].Altogether, we conclude thatJ(π ⋆ ) -J( π) ≤ E π [∆ H ⋆ (o)] + R • P π [H ⋆ ≤ H]. Proof of Lemma G.6. Let us define f (o) = H h=1 E[r h | x h , a h ] and g(o) = I{H ⋆ > H}; note that g(o) is indeed a measurable function of o = (x 1 , a 1 ), . . . , (x H , a H ), since I{H ⋆ > H} = 1 -I{H ⋆ ≤ H}, {H ⋆ ≤ H} = ∪ h≤H {H ⋆ =h}, and {H ⋆ = h} is a measurable function of (x 1 , a 1 ), . . . , (x h , a h ). We can writeEQUATIONLet us adopt the shorthand P (x 1:H | a 1:H-1 ) := H-1 h=0 P h (x h+1 | x h , a h ). We can bound the first term in Eq. ( 18) viaE π H h=1 r h I{H ⋆ > H} = o=x 1:H ,a 1:H f (o)g(o)P (x 1:H | a 1:H-1 ) H h=1 π h (a h | x 1:h , a 1:h-1 ) = o=x 1:H ,a 1:H f (o)g(o)P (x 1:H | a 1:H-1 ) H h=1 π h (a h | x h ) ≤ o=x 1:H ,a 1:H f (o)P (x 1:H | a 1:H-1 ) H h=1 π h (a h | x h ) = E π H h=1 r h = J( π),where the second equality uses that π(• | x 1:h , a 1:h-1 ) = π(• | x h ) for all h ∈ [H] whenever g(o) = 1.To bound the second term in Eq. ( 18), we can writeP π [H ⋆ ≤ H] = H h=1 P π [H ⋆ = h].For each h, let o h := (x 1 , a 1 ), . . . , (x h , a h ) and g h (o h ) := I{H ⋆ = h} (recall that I{H ⋆ = h} is a measurable function of (x 1 , a 1 ), . . . , (x h , a h )). Note that for each h, if we define P (x1:h | a 1:h-1 ) := h-1 h=0 P ℓ (x ℓ+1 | x ℓ , a ℓ ), then P π [H ⋆ = h] = o h =x 1:h ,a 1:h g h (o h )P (x 1:h | a 1:h-1 ) h ℓ=1 π ℓ (a ℓ | x 1:ℓ , a 1:ℓ-1 ) = o h =x 1:h ,a 1:h g h (o h )P (x 1:h | a 1:h-1 ) h ℓ=1 π ℓ (a ℓ | x ℓ ) = P π [H ⋆ = h],where the second inequality uses that π(• | x 1:ℓ , a 1:ℓ-1 ) = π(• | x ℓ ) whenever ℓ ≤ H ⋆ .Proof of Lemma G.7. We start by writingE π [∆ H ⋆ (o)] = H+1 h=1 E π [I{H ⋆ = h}∆ h (o)]. For each h ≤ H + 1, let o h := (x 1 , a 1 ), . . . , (x h , a h ) and g h (o h ) := I{H ⋆ = h} (recall that I{H ⋆ = h} is a measurable function of (x 1 , a 1 ), . . . , (x h , a h )). For each h ≤ H + 1, if we define P (x 1:h | a 1:h-1 ) := h-1 h=0 P ℓ (x ℓ+1 | x ℓ , a ℓ ), then E π [I{H ⋆ = h}∆ h (o)] = o h =x 1:h ,a 1:h g h (o h )∆ h (o h )P (x 1:h | a 1:h-1 ) h ℓ=1 π ℓ (a ℓ | x 1:ℓ , a 1:ℓ-1 ) = o h =x 1:h ,a 1:h g h (o h )∆ h (o h )P (x 1:h | a 1:h-1 ) h ℓ=1 π ℓ (a ℓ | x ℓ ) = E π [I{H ⋆ = h}∆ h (o)],where the second inequality uses that π(• | x 1:ℓ , a 1:ℓ-1 ) = π(• | x ℓ ) whenever ℓ ≤ H ⋆ .Lemma G.4 is proven using arguments similar to those in Zhang et al. [104, 105] , but requires non-trivial modifications to accommodate the fact that π is an arbitrary, potentially suboptimal policy.Proof of Lemma G.4. Let us abbreviate Q = Q π and V = V π . Assume without loss of generality that R = 1, and note that this implies that r h ∈ [0, 1] and Q h , V h ∈ [0, 1], which we will use throughout the proof.h-1 := σ((x 1 , a 1 , r 1 ), . . . , (x h-1 , a h-1 , r h-1 ), x h ). Since E h-1 [Q h (x h , a h ) -V h (x h )] = 0, two applications of Lemma D.2 and a union bound imply that with probability at least 1δ, for allH ′ ∈ [H] H ′ h=1 Q h (x h , a h ) -V h (x h ) ≤ H ′ h=1 E π (Q h (x h , a h ) -V h (x h )) 2 | x h + log(2δ -1 ). Since E π [Q h (x h , a h ) | x h ] = V h (x h ), we can write H ′ h=1 E π (Q h (x h , a h ) -V h (x h )) 2 | x h = H ′ h=1 E π (Q 2 h (x h , a h ) | x h -V 2 h (x h ) = H ′ h=1 E π (Q 2 h (x h , a h ) | x h -V 2 h+1 (x h+1 ) + V 2 H ′ +1 (x H ′ +1 ) -V 2 1 (x 1 ) ≤ H ′ h=1 E π (Q 2 h (x h , a h ) | x h -V 2 h+1 (x h+1 ) + 1.Observe that by Jensen's inequality, we haveE π (Q 2 h (x h , a h ) | x h ≤ E π (r h + V h+1 (x h+1 )) 2 | x h = E π V 2 h+1 (x h+1 ) | x h + E π r 2 h | x h + 2 E π [r h V h+1 (x h+1 ) | x h ] ≤ E π V 2 h+1 (x h+1 ) | x h + 3 E π [r h | x h ], so that H ′ h=1 E π (Q h (x h , a h ) -V h (x h )) 2 | x h ≤ H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -V 2 h+1 (x h+1 ) + 3 H ′ h=1 E π [r h | x h ] + 1.By Lemma D.3, we have that with probability at least 1δ, for allH ′ ∈ [H], H ′ h=1 E π [r h | x h ] ≤ 3 2 H ′ h=1 r h + 4 log(2δ -1 ) ≤ 3 2 + 4 log(2δ -1 ).Likewise, by Lemma D.2, we have that with probability at least 1δ, for allH ′ ∈ [H], H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -V 2 h+1 (x h+1 ) ≤ H ′ h=1 E π V 2 h+1 (x h+1 ) -E π V 2 h+1 (x h+1 ) | x h 2 | x h + log(δ -1 ) = H ′ h=1 Var π V 2 h+1 (x h+1 ) | x h + log(δ -1 ) ≤ 4 H ′ h=1 Var π [V h+1 (x h+1 ) | x h ] + log(δ -1 ),where the last line uses the following lemma, proven in the sequel.Lemma G.8. If X is a random variable with |X| ≤ 1, then Var(X 2 ) ≤ 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 δ ∈ (0, 1), with probability at least 1 -2δ, for allH ′ ∈ [H], H ′ h=1 Var π V π h+1 (x h+1 ) | x h ≤ 8 + 32 log(2δ -1 ).Putting together all of the developments so far, we have that with probability at least 1 -5δ, for allH ′ ∈ [H], H ′ h=1 Q h (x h , a h ) -V h (x h ) ≤ 4 H ′ h=1 Var π [V h+1 (x h+1 ) | x h ] + 6 + 14 log(2δ -1 )≤ 38 + 142 log(2δ -1 ).Proof of Lemma G.8. Note that we haveVar(X 2 ) = E (X 2 -E X 2 ) 2 ≤ E (X 2 -E[X] 2 ) 2 ≤ 4 E (X -E[X]) 2 ,where the last line uses thata 2 -b 2 ≤ 2|a -b| for a, b ∈ [-1, 1].Proof of Lemma G.9. Abbreviate V ≡ V π . By telescoping, we can writeZ H ′ := H ′ h=1 Var π [V h+1 (x h+1 ) | x h ] = H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -(E π [V h+1 (x h+1 ) | x h ]) 2 = H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -V 2 h+1 (x h+1 ) + H ′ h=1 V 2 h (x h ) -(E π [V h+1 (x h+1 ) | x h ]) 2 + V 2 H ′ +1 (x H ′ +1 ) -V 2 1 (x 1 ) ≤ H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -V 2 h+1 (x h+1 ) + H ′ h=1 V 2 h (x h ) -(E π [V h+1 (x h+1 ) | x h ]) 2 + 1.For the latter term, sincea 2 -b 2 ≤ 2|a -b| for a, b ∈ [0, 1],we have thatH ′ h=1 V 2 h (x h ) -(E π [V h+1 (x h+1 ) | x h ]) 2 ≤ 2 H ′ h=1 |V h (x h ) -E π [V h+1 (x h+1 ) | x h ]| = 2 H ′ h=1 |E π [r h | x h ]| ≤ 2 H ′ h=1 E π [r h | x h ],By Lemma D.3, we have that with probability at least 1δ, for all H ′ ∈ [H],H ′ h=1 E π [r h | x h ] ≤ 3 2 H ′ h=1 r h + 4 log(2δ -1 ) ≤ 3 2 + 4 log(2δ -1 ).For the first term, by Lemma D.2, we have that for all η ∈ (0, 1), with probability at least 1δ, for allH ′ ∈ [H], H ′ h=1 E π V 2 h+1 (x h+1 ) | x h -V h+1 (x h+1 ) ≤ η H ′ h=1 E π V 2 h+1 (x h+1 ) -E π V 2 h+1 (x h+1 ) | x h 2 | x h + η -1 log(δ -1 ) = η H ′ h=1 Var π V 2 h+1 (x h+1 ) | x h + η -1 log(δ -1 ) ≤ 4η H ′ h=1 Var π [V h+1 (x h+1 ) | x h ] + η -1 log(δ -1 ) = 4ηZ H ′ + η -1 log(δ -1 ),where the last inequality uses Lemma G.8. Putting everything together and setting η = 1/8, we conclude that with probability at least 1 -2δ, for allH ′ ∈ [H] Z H ′ ≤ 1 2 Z H ′ + 16 log(2δ -1 ) + 4,which yields the result after rearranging.The following result shows that the dependence on the variance in Corollary 2.1 cannot be improved in general, which implies that the horizon-dependence in this regime is tight. π ⋆ ≤ σ 2 and µ ≤ σ 2 /H, and for whichP J(π ⋆ ) -J( π) ≥ c • σ 2 n ≥ 1 8for an absolute constant c ≥ 1.Beyond showing that a slow 1/ √ n rate is required for stochastic policies, 21Proof of Theorem G.1.For this proof, we consider a slightly more general online imitation learning model in which the learner is allowed to select a i h based on the sequence(x i 1 , a i 1 , a ⋆,i 1 ), . . . , (x i h-1 , a i h-1 , a ⋆,i h-1), (x i h , a ⋆,i h ) at training time; this subsumes the offline imitation learning model. Let H ∈ N, n ∈ N, and σ 2 ∈ [H, H 2 ] be given. Fix a parameter K ∈ N such that H/K is an integer and a parameter ∆ ∈ (0, 1/2) be fixed; both parameters will be chosen at the end of the proof.We first specify the dynamics for the reward-free MDP M ⋆ and the policy class Π. Let A = {a, b}, and let X = {s, a, b}. We consider the following (deterministic) dynamics. For h ∈ H := [1, K + 1, 2K + 1, . . .], always the state is always x h = s. For such a step h ∈ H, choosing a h = a sets x h = a for the next K -1 steps until returning to s at time h + K, and choosing a h = b sets x h = b until returning to s at time h + K (that is, the action has no effect for h / ∈ H).We consider a class Π = {π a , π b } consisting of two experts π a and π b . π a sets π a h (a | s) = 1 2 + ∆ for h ∈ H and sets π h (x) = a for all h / ∈ H and x ∈ X . Meanwhile, π b sets π b (b | s) = 1 2 + ∆ for h ∈ H and sets π h (x) = a for all h / ∈ H and x ∈ X .We consider two choices of reward function, r a and r b . r a sets r a h (s, a) = 1 and r a h (s, b) = 0 for h ∈ H, and sets r a h (a, •) = 1 and r a h (b,•) = 0 for h / ∈ H. Meanwhile, r b sets r b h (s, b) = 1 and r b h (s, a) = 0 for h ∈ H and sets r b h (a, •) = 0 and r b h (b, •) = 1 for h / ∈ H.Let a problem instance I = (M ⋆ , r, π ⋆ ) refer to a tuple consisting of the reward-free MDP M ⋆ , a reward function r = {r h } H h=1 , and an expert policy π ⋆ . We consider four problem instances altogether: (M ⋆ , r a , π a ), (M ⋆ , r b , π a ), (M ⋆ , r a , π b ), and (M ⋆ , r b , π b ).Let P a denote the law of o 1 , . . . , o n when a when we execute 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 a [•] and E b [•] denote the corresponding expectations. In addition, for any policy π, let P π a |π denote the law of o = (x 1 , a 1 , a ⋆ 1 ), . . . , (x H , a H , a ⋆ H ) when we execute π in the online imitation learning framework and the expert policy is π ⋆ = π a , and define P π b |π analogously.We begin by lower bounding the regret. Consider a fixed policy π = { π h : X → ∆(X )}, and let π(a) := 1 |H| h∈H π h (a | s). Observe that for instance (M ⋆ , r a , π a ), we haveJ r a (π a ) -J r a ( π) = 1 2 + ∆ H -K h∈H π h (a | s) = 1 2 + ∆ H -Hπ(a)and for instance (M ⋆ , r b , π a ),J r b (π a ) -J r b ( π) = 1 2 -∆ H -K h∈H π h (b | s) = Hπ(a) - 1 2 + ∆ H.Likewise, for instance (M ⋆ , r b , π b ), we haveJ r b (π b ) -J r b ( π) = 1 2 + ∆ H -K h∈H π h (b | s) = π(a)H - 1 2 -∆ H and for instance (M ⋆ , r a , π b ), J r a (π b ) -J r a ( π) = 1 2 -∆ H -K h∈H π h (a | s) = 1 2 -∆ H -π(a)H.We conclude that for any ε > 0, since the law of the dataset is independent of the choice of the reward function,max{P a [J r a (π a ) -J r a ( π) ≥ εH], P a [J r b (π a ) -J r b ( π) ≥ εH], P b [J r b (π b ) -J r b ( π) ≥ εH], P b [J r a (π b ) -J r a ( π) ≥ εH]} ≥ max        P a 1 2 + ∆ H -π(a)H ≥ εH , P a π(a)H - 1 2 + ∆ H ≥ εH , P b π(a)H - 1 2 -∆ H ≥ εH , P b 1 2 -∆ H -π(a)H ≥ εH        ≥ 1 2 max P a 1 2 + ∆ -π(a) H ≥ εH , P b π(a) - 1 2 -∆ H ≥ εH = 1 2 max P a 1 2 + ∆ -π(a) ≥ ε , P b π(a) - 1 2 -∆ ≥ ε ≥ 1 4 P a 1 2 + ∆ -π(a) ≥ ε + P b π(a) - 1 2 -∆ ≥ ε ≥ 1 4 1 -P a 1 2 + ∆ -π(a) ≤ ε + P b π(a) - 1 2 -∆ ≥ ε ≥ 1 4 1 -P a 1 2 -∆ -π(a) ≥ ε + P b π(a) - 1 2 -∆ ≥ ε ≥ 1 4 (1 -D TV (P a , P b )),where the second inequality uses the union bound (i.e.P[|x| ≥ ε] = P[x ≥ ε ∪ -x ≥ ε] ≤ P[x ≥ ε] + P[-x ≥ ε]), and the second-to-last inequality holds as long as ε < ∆. In particular, this implies that max       P a J r a (π a ) -J r a ( π) ≥ ∆H 2 , P a J r b (π a ) -J r b ( π) ≥ ∆H 2 , P b J r b (π b ) -J r b ( π) ≥ ∆H 2 , P b J r a (π b ) -J r a ( π) ≥ ∆H 2        ≥ 1 4(1 -D TV (P a , P b )).Next, using Lemma D.2 of Foster et al. [36] , we can boundD 2 TV (P a , P b ) ≤ D 2 H (P a , P b ) ≤ 7 E a n i=1 D 2 H P π a |π i , P π b |π i .Observe that for a given episode i, regardless of how the policy π i is selected:• The feedback for steps h / ∈ H is identical under P a and P b .• The feedback at step h ∈ H differs only in the distribution of a ⋆ h ∼ π a (s) versus a ⋆ h ∼ π b (s). This is equivalently to Ber( 1 /2 + ∆) feedback versus Ber( 1 /2 -∆) feedback.As a result, using Lemma D.2 of Foster et al. [36] once more, we haveD 2 H P π a |π i , P π b |π i ≤ 7 h∈H D 2 H (Ber( 1 /2 + ∆), Ber( 1 /2 -∆))Since ∆ ∈ (0, 1/2), we have D 2 H (Ber( 1 /2 + ∆), Ber( 1 /2 -∆)) ≤ O(∆ 2 ) (e.g., Foster et al. [34, Lemma A.7] ). We conclude thatD 2 TV (P a , P b ) ≤ O n • |H| • ∆ 2 = O n • H K • ∆ 2We set ∆ 2 = c • K Hn for c > 0 sufficiently small so that D 2 TV (P a , P b ) ≤ 1/2, and conclude that on at least one of the four problem instances, the algorithm must haveJ(π ⋆ ) -J( π) ≥ Ω(∆H) = ΩHK n 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, we haveQ π ⋆ h (x h , π ⋆ (x h )) -Q π ⋆ h (x h , a) = 0 for h / ∈ H, while Q π ⋆ h (x h , π ⋆ (x h )) -Q π ⋆ h (x h , a) ≤ Kfor h ∈ H, so we can take µ ≤ K. Consequently, we haveσ 2 π ⋆ = H h=1 E π ⋆ (Q π ⋆ h (x h , π ⋆ (x h )) -Q π ⋆ h (x h , a h )) 2 ≤ h∈H E π ⋆ (Q π ⋆ h (s, π ⋆ (s)) -Q π ⋆ h (s, a h )) 2 ≤ H K • K 2 = HK.We conclude by setting K = σ 2 /H, which is admissible for σ 2 ∈ H, H 2 (up to a loss in absolute constants, we can assume that σ 2 /H is an integer without loss of generality).Proof of Proposition 3.1. We haveσ 2 π ⋆ = H h=1 E π ⋆ (Q π ⋆ h (x h , a h ) -V π ⋆ h (x h )) 2 . Note that Q π ⋆ h (x h , a h ) = E r h + V π ⋆ h (x h+1 ) | x h , a h .Hence, by Jensen's inequality we can boundE π ⋆ (Q π ⋆ h (x h , a h ) -V π ⋆ h (x h )) 2 ≤ E π ⋆ E (r h + V π ⋆ h+1 (x h+1 ) -V π ⋆ h (x h )) 2 | x h , a h = E π ⋆ E π ⋆ (r h + V π ⋆ h+1 (x h+1 ) -V π ⋆ h (x h )) 2 | x h = E π ⋆ Var π ⋆ r h + V π ⋆ h+1 (x h+1 ) | x h , so that σ 2 π ⋆ ≤ E π ⋆ H h=1 Var π ⋆ r h + V π ⋆ h+1 (x h+1 ) | x h ≤ E π ⋆ H h=0 Var π ⋆ r h + V π ⋆ h+1 (x h+1 ) | x h = Var π ⋆ H h=1 r h ≤ R 2 ,where the second to last inequality follows from Lemma D.5.Additional ResultsThis 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 an 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 on a per-policy basis.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 in every episode. In this section, we consider a 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 i ∈ [n] the learner executes a policy π i = {π i h : X → ∆(A)} H h=1 , and at any step h in the episode, they can decide whether to query the expert for an action a ⋆ h ∼ π ⋆ h (x h ) at the current state x h . We set M i = 1 if the learner queries the expert at any point during episode i and set M i = 0 otherwise, and define the active sample complexity M := n i=1 M i as the total number of queries. It is clear that the active sample complexity satisfies m ≤ n, and in some cases we might hope for it to be much smaller than the total number of episodes, at least for a well-designed algorithm. While this can 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 a logarithmic factor), meaning that online interaction in the active sample complexity framework cannot improve over LogLossBC in general. E[J(π ⋆ ) -J( π)] ≥ c • H mfor an absolute constant c > 0. In addition, the dynamics, rewards, and expert policies are all stationary.Since this example has log|Π| = log(M ), it follows that the sample complexity bound for LogLossBC in Theorem 2.1 (which uses M = n) can be improved by no more than a log(n) factor through online interaction in the active framework.Proof of Theorem H.1. Let m ∈ N and H ∈ N be fixed. We first specify the dynamics for the reward-free MDP M ⋆ . Set X = {x 1 , . . . , x m } and A = {a, b}. The initial state distribution is P 0 = unif(x 1 , . . . , x m ). The transition dynamics are P h (x ′ | x, a) = I{x ′ = x} for all h; that is, x 1 , . . . , x m are all self-looping terminal states.Let a problem instance I = (M ⋆ , r, π ⋆ ) refer to a tuple consisting of the reward-free MDP M ⋆ , a reward function r = {r h } H h=1 , and an expert policy π ⋆ . We consider m + 1 problem instances I 0 , . . . , I m parameterized by a collection of policies Π = {π 0 , . . . , π m } and reward functions R = {r 0 , . . . , r m }.• For problem instance I 0 = (M ⋆ , r 0 , π 0 ), the expert policy is π 0 , which sets π 0 h (x) = a for all x ∈ X and h ∈ [H]. The reward function r 0 sets r h (x, a) = I{a = a} for all x ∈ X and h ∈ [H].• For each problem instance I j = (M ⋆ , r j , π j ), the expert policy is π j , which for all h ∈ [H] sets π j h (x) = a for x ̸ = x j and sets π h (x j ) = b. The reward function r j sets r h (x, a) = I{a = a, x ̸ = x j } + I{a = b, x = x j } for all h ∈ [H]. Let J j denote the expected reward under instance j. Note that all instances satisfy µ = 1, and that π j is an optimal policy for each instance j.Going forward, we fix the online imitation learning algorithm under consideration and let P j denote the law of o 1 , . . . , o n when a when we execute the algorithm on instance I j ; let E j [•] denote the corresponding expectation. In addition, for any policy π, let P π j |π denote the law of o = (x 1 , a 1 , a ⋆ 1 ), . . . , (x H , a H , a ⋆ H ) when we execute π in the online imitation learning framework when the underlying instance is I j , with the convention that a ⋆ h =⊥ if the learner does not query the expert in episode j.Our aim is to lower bound max j∈{0,...,m}E j [J j (π j ) -J j ( π)] To this end, define ρ j (π, π ′ ) = H h=1 E a h ∼π h (xj ),a ′ h ∼π ′ h (xj ) I{a h ̸ = a ′ h } and ρ(π, π ′ ) = 1 m ρ j (π, π ′), and observe thatE 0 [J 0 (π 0 ) -J 0 ( π)] = E 0   1 m m j=1 H h=1 E a h ∼ π h (xj ) [I{a h ̸ = π 0 h (x j )}]   = E 0 [ρ( π, π 0 )] ≥ H 2m • P 0 ρ( π, π 0 ) ≥ H 2m .Next, note that for any i ∈ [m], if ρ( π, π 0 ) < H 2m , then ρ j ( π, π 0 ) < H 2 , which means that ρ j ( π, π j ) ≥ H 2 . It follows thatE j [J j (π j ) -J j ( π)] = E j 1 m ρ j ( π, π j ) ≥ H 2m P j ρ( π, π 0 ) < H 2m ,and if we define P = E j∼unif([m]) P j , thenE j∼unif([m]) E j [J j (π j ) -J j ( π)] ≥ H 2m P ρ( π, π 0 ) < H 2m .Combining these observations, we find that max i∈{0,...,m}E j [J j (π j ) -J j ( π)] ≥ H 4m P 0 ρ( π, π 0 ) ≥ H 2m + P ρ( π, π 0 ) < H 2m ≥ H 4m (1 -D TV P 0 , P ).It remains to bound the total variation distance. Next, using Lemma D.2 of Foster et al. [36] , we can boundD 2 TV P 0 , P ≤ D 2 H P 0 , P ≤ E j∼unif[m] D 2 H (P 0 , P j ) ≤ 7 E j∼unif[m] E 0 n t=1 D 2 H P π 0 |π t , P π j |π t .Since the feedback the learner receives for a given episode t is identical under instances I 0 and I j is identical unless i) x 1 = x j , and ii) the learner decides to query the expert for feedback (i.e., M t = 1), we can boundD 2 H P π 0 |π t , P π j |π 0 ≤ 2P π 0 |π t [x t 1 = x j , M t = 1]and henceE j∼unif[m] E 0 n t=1 D 2 H P π 0 |π t , P π j |π t ≤ 2 E j∼unif[m] E 0 n t=1 P π 0 |π t [x t 1 = x j , M t = 1] = 2 m E 0   n t=1 m j=1 P π 0 |π t [x t 1 = x j , M t = 1]   = 2 m E 0 n t=1 P π 0 |π t [M t = 1] = 2 m E 0 [M ].It follows that if E 0 [M ] ≤ m/56, then D TV P 0 , P ≤ 1/2, so that the algorithm must have max i∈{0,...,m}E j [J j (π j ) -J j ( π)] ≥ H 8m .In this section, we further investigate the optimality of LogLossBC for stochastic experts (Theorem 3.1). Recall that when log|Π| = O(1) the leading-order term in Theorem 3.1 scales as roughly σ 2 π ⋆ /n, where the salient quantity is the varianceσ 2 π ⋆ := H h=1 E π ⋆ (Q π ⋆ h (x h , π ⋆ (x h )) -Q π ⋆ h (x h , a h )) 2for the expert policy π ⋆ . Theorem G.1 shows that this is optimal qualitatively, in the sense that for any value σ 2 , there exists a class of MDPs where the σ 2 π ⋆ ≤ σ 2 , and where the minimax rate is at least σ 2 /n.In 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 x h = a 1:h-1 ; cf. Appendix B.3), Theorem G.1 is optimal on a per-policy basis. Concretely, we prove a local minimax lower bound [28] which states that for any policy π ⋆ and any reward function r ⋆ , there exists a difficult "alternative" policy π, such that in worst case over rewards r ∈ {-r ⋆ , +r ⋆ } and expert policies π ∈ {π ⋆ , π}, any algorithm must have regret at least σ 2 /n. Theorem H.2. Consider the offline imitation learning setting, and let M ⋆ be an autoregressive MDP. Let a reward function r ⋆ with H h=1 r ⋆ h ∈ [0, R] almost surely be fixed, and let an expert policy π ⋆ be given. For any n ∈ N, there exists an alternative policy π such thatmin Alg max π∈{π ⋆ , π} max r∈{r ⋆ ,-r ⋆ } P J(π) -J( π) ≥ c • σ 2 π ⋆ n ≥ 1 4 for all n ≥ c ′ • R 2 σ 2 π ⋆, where c, 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 n≥ c ′ • R 2 σ 2 π ⋆in Theorem H.2 is somewhat natural, as this corresponds to the regime in which the σ 2 π ⋆ /n term in Theorem 3.1 dominates the lower-order term.Proof of Theorem H.2. We begin by observing that for any ∆ > 0, minAlg max π∈{π ⋆ , π} max r∈{r ⋆ ,-r ⋆ } P[J r (π) -J r ( π) ≥ ∆] ≥ min Alg max π∈{π ⋆ , π} P[|J r ⋆ (π) -J r ⋆ ( π)| ≥ ∆].with the convention that J r (π) denotes the expected reward under r; we abbreviate J(π) ≡ J r ⋆ (π) going forward. Let P π n denote the law of the offline imitation learning dataset under π. If we set ∆ = |J(π ⋆ ) -J( π)|/2, then by the standard Le Cam two-point argument, we have thatmax P π ⋆ n [|J(π ⋆ ) -J( π)| ≥ ∆], P π n [|J( π) -J( π)| ≥ ∆] ≥ 1 2 1 -P π ⋆ n [|J(π ⋆ ) -J( π)| < ∆] + P π n [|J( π) -J( π)| ≥ ∆] ≥ 1 2 1 -P π ⋆ n [|J( π) -J( π)| ≥ ∆] + P π n [|J( π) -J( π)| ≥ ∆] ≥ 1 2 1 -D TV P π ⋆ n , P π n ≥ 1 2 1 -n • D 2 H (P π ⋆ , P π ) ,where the final inequality uses the standard tensorization property for Hellinger distance (e.g., Wainwright [91] ).We will proceed by showing thatEQUATIONfor any ε > 0 sufficiently small, from which the result will follow by setting ε 2 ∝ 1/n andπ = arg max π |J(π) -J(π ⋆ )| | D 2 H P π ⋆ , P π ≤ ε 2 ≥ Ω(1) • σ 2 π ⋆ • ε 2 .To prove this, we will appeal to the following technical lemma.Lemma H.1. For any distribution Q and function h with |h| ≤ R almost surely, it holds that for all0 ≤ ε 2 ≤ Var Q [h] 4R 2 , there exists a distribution P such that 1. E P [h] -E Q [h] ≥ 2 -3 Var Q [h] • ε 2 2. D KL (Q ∥ P) ≤ ε 2 .Since stochastic policies π in the autoregressive MDP M ⋆ are equivalent to arbitrary joint laws over the sequence a 1:H (via Bayes' rule) and J(π) = E π H h=1 r ⋆ h , Lemma H.1 implies that for any ε 2 ≤ Var π ⋆ H h=1 r ⋆ h /4R 2 , there exists a policy π such that (i) D 2 H P π ⋆ , P π ≤ D KL P π ⋆ ∥ P π ≤ ε 2 , and (ii)J( π) -J(π ⋆ ) ≥ 2 -3 Var π ⋆ H h=1 r ⋆ h • ε 2 .This establishes Eq. (19) . The result now follows by setting ε 2 = c n for an absolute constant c > 0 so that n• D 2 H (P π ⋆ , P π ) ≤ 1/2, which is admissible whenever n ≥ c ′ • R 2 σ 2 π ⋆. Finally, we observe that for any deterministic MDP, by Lemma D.5,Var π ⋆ H h=1 r h = E π ⋆ H h=1 Var π ⋆ r h + V π ⋆ h+1 (x h+1 ) | x h = E π ⋆ H h=1 (Q π ⋆ h (x h , a h ) -V π ⋆ h (x h )) 2 = σ 2 π ⋆ , since deterministic MDPs satisfy Q π ⋆ h (x h , a h ) = r h (x h , a h ) + V π ⋆ h+1 (x h+1 ) almost surely, and since E π ⋆ Q π ⋆ h (x h , a h ) | x h = V π ⋆ h (x h ).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 P via the probability mass function p(x) = q(x)e ηh(x)x ′ q(x ′ )e ηh(x ′ )for a parameter η > 0. We begin by observing thatD KL (Q ∥ P) = log E Q e ηh -η E Q [h] = log E Q e η(h-E Q [h]) .We now use the following lemma.Lemma H.2. For any random variable X with |X| ≤ R almost surely and any η ∈ (0, (2R) -1 ),η 2 8 Var[X] ≤ log E e η(X-E[X]) ≤ η 2 Var[X].Hence, as long as η ≤ (2R) -1 ,D KL (Q ∥ P) ≤ η 2 Var Q [h].We set η = minε 2 Var Q [h] , 1 2R so that D KL (Q ∥ P) ≤ ε 2 .Next, we compute that0 ≤ D KL (P ∥ Q) = η E P [h] -log E Q e ηh ,so thatE P [h] -E Q [h] ≥ η -1 log E Q e ηh -E Q [h] = η -1 log E Q e η(h-E Q [h]) . Since η ≤ (2R) -1 , Lemma H.2 yields E P [h] -E Q [h] ≥ η 8 Var Q [h] = 1 8 Var Q [h] • ε 2 as long as ε 2 ≤ Var Q [h] 4R 2 .Proof of Lemma H.2. Note that e x ≤ 1 + x + (e -2)x 2 ≤ 1 + x + x 2 whenever |x| ≤ 1, and similarly ex ≥ 1 + x + x 2 4 for |x| ≤ 1. It follows that if η ≤ (2R) -1 , 1 + η 2 4 Var(X) ≤ E e η(X-E[X]) ≤ 1 + η 2 Var(X).We conclude by using that x 2 ≤ log(1 + x) ≤ x for x ∈ [0, 1].Theorem 2.1 and Theorem 3.1 are supervised learning reductions that bound the regret of any policy π in terms of its Hellinger distance D 2 H P π , P π ⋆ to the expert policy π ⋆ . The following result shows that these reductions are tight in a fairly strong instance-dependent 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 h=1 for which each term in Eq. ( 9) of Theorem 3.1 is tight, and such that Theorem 2.1 is tight; the only caveat is that we require the reward function to be non-Markovian, in the sense that r h depends on the full history x 1:h and a 1:h . Theorem H.3 (Converse to Theorems 2.1 and 3.1). Let a reward-free MDP M ⋆ and a pair of (potentially stochastic) policies π and π ⋆ be given.1. For any R > 0, there exists a non-Markovian reward function rEQUATION2. For any σ 2 > 0, there exists a non-Markovian reward function rEQUATION3. For any R > 0 and σ 2 > 0, there exists a non-Markovian reward function r= {r h } H h=1 with H h=1 r h ∈ [0, R] and σ 2 π ⋆ ≤ σ 2 simultaneously such that J(π ⋆ ) -J( π) ≥ 1 9 min σ 2 • D 2 H (P π , P π ⋆ ), R • D 2 H P π , P π ⋆ .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. ( 9) or Theorem 3.1 is tight.Note that for some MDPs, the state x h already contains the full history x 1:h-1 , a (P + Q). Consider the function h = 1 - 1 2 Q P ∈ [0, 1].Using Lemma D.4, we observe thatEQUATIONWe also observe that by concavity of variance,EQUATIONTo apply this observation to the theorem at hand, let a parameter B > 0 be given, let P := 1 2 (P π ⋆ +P π ), and consider the non-Markov reward function r that sets r 1 , . . . , r h-1 = 0 andr H (τ ) = B • 1 - 1 2 P π P ∈ [0, B].Then by Eq. ( 22), we have thatJ(π ⋆ ) -J( π) ≥ B 6 • D 2 H P π , P π ⋆ .At the same time, by Eq. ( 23), we have thatVar π ⋆ H h=1 r h = Var π ⋆ [r H ] ≤ 2B 2 • D 2 H P π , P π ⋆ ,and by Proposition 3.1,σ 2 π ⋆ ≤ Var π ⋆ H h=1 r h .22 Note that since the reward function under consideration is non-Markovian, the value functions Q π ⋆ h and V π ⋆ h depend on the full history x 1:h , a 1:h-1 .To conclude, note that if we setB 2 = R 2 , then H h=1 r h ∈ [0, R] and J(π ⋆ ) -J( π) ≥ R 6 • D 2 H P π , P π ⋆ .Meanwhile, if we setB 2 = σ 2 2D 2 H (P π , P π ⋆ ) , then σ 2 π ⋆ ≤ σ 2 and J(π ⋆ ) -J( π) ≥ 1 9 σ 2 • D 2 H (P π , P π ⋆ ).Finally, if we setEQUATIONEQUATION• D 2 H P π , P π ⋆ .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 a problem-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 a policy class-dependent fashion not captured by existing theory. In particular, we identify three phenomena which lead to improved sample complexity: (i) representational benefits; (ii) value-based feedback; 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.This paper (for both deterministic and stochastic experts) focuses on the realizable setting in which π ⋆ ∈ Π. It is natural to 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 to different forms of horizon dependence. For example, for deterministic experts, if Π is misspecified in the sense that inf π∈Π L bc (π) ≤ ε apx , the indicator-loss behavior cloning algorithm in ?? achievesJ(π ⋆ )-J( π) ≲ RH • log(|Π|δ -1 )n + ε apx , which is tight in general. In other words, the dependence on ε apx is not horizon-independent. On the other hand, as we show in Appendix E, if we assume that inf π∈Π D χ 2 P π ⋆ ∥ P π ≤ ε apx , a stronger notion of misspecification error, then LogLossBC achieves a horizon-independent guarantee of the form J(π ⋆ ) -J( π) ≲ R • log(|Π|δ -1 ) n + ε apx . 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-independent treatment for the realizable setting, we hope that our results can serve as a starting point.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 2 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.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 I.3 (Benefits of exploration for online IL). For any n ∈ N and H ∈ N, there exists an MDP M ⋆ and a class of deterministic policies Π with |Π| = 2 with the following properties.1. There exists an online imitation learning algorithm that returns a policy π such that J(π ⋆ ) -J( π) = 0 with probability at least 1δ using O(log(δ -1 )) episodes, for all possible reward functions (i.e., even if µ = H).2. For any offline imitation learning algorithm, there exists a deterministic reward function r = {r h } H h=1 and expert policy π ⋆ ∈ Π with µ = 1 such that any algorithm must haveE[J(π ⋆ ) -J( π)] ≥ Ω(1) • H n . In addition, Dagger has regret E[J(π ⋆ ) -J( π)] ≥ Ω(1) • H n .The idea behind this construction is simple: We take the lower bound construction from Theorem 2.2 and augment it with a "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 a well-designed online IL algorithm that deliberately navigates to the revealing state can use it to identify π ⋆ extremely quickly.As with the previous examples, this construction is 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. • The dynamics are as follows. We have x 1 = x deterministically. For simplicity, we assume that only actions in [N ] are available at step h = 1. If a 1 ∈ S, then x 2 = y, otherwise x 2 = z.• The reward at step 1 is r 1 (•, •) = 0, and the reward at step 2 is given by r 2 (y, •) = 1 and r 2 (z, a) = I{a = a ⋆ }.• The expert π ⋆ sets π ⋆ (x) = unif(S), π ⋆ (y) = unif({a, b}), and π ⋆ (z) = a ⋆ .Let us refer to the problem instance above as I S,a ⋆ = (M S,a ⋆ , π ⋆ S,a ⋆ , r S,a ⋆ ) , and let J S,a ⋆ (π) denote the expected reward under this instance.Upper bound for online imitation learning. Consider the algorithm that sets πi 1 = unif([N ]) for each i ∈ [n].If we play for n = log 2 (δ -1 ) episodes, we will see x 2 = z in at least one episode with probability at least 1δ, at which point we will observe a ⋆ = π ⋆ (z), and we can return the policy π that sets π 1 (x) = unif([N ]) and π 2 (•) = a ⋆ ; this policy has zero regret.Note that if we define Π = π ⋆ S,a ⋆ |S|=N/2,a ⋆ ∈{a,b} as the natural policy class for the family of instances above, then the algorithm above is equivalent to running Dagger with the online learning algorithm that, at iteration i, setsπ i h = unif π ∈ Π h | π 2 (z) = a ⋆,j 2 ∀j < i : x j 2 = z ,and choosing the final policy as π = π i for any iteration i after x 2 = z is encountered.Lower bound for offline imitation learning. Consider the offline imitation learning setting. When the underlying instance is I S,a ⋆ , we observe a dataset D consisting of n trajectories generated by executing π ⋆ S,a ⋆ in M S,a ⋆ . The trajectories never visit the state z, so a ⋆ is not identifiable, and we can do no better than guessing a ⋆ uniformly in this state. Letting E S,a ⋆ denote the law of D under instance I S,a ⋆ , we have J S,a ⋆ ( π) = π 1 (S | x) + π 1 (S c | x) π 2 (a ⋆ | z). It follows that for any S, since the law of D does not depend on a ⋆ , max Note that if π is proper in the sense that π 1 (•x) = unif( S) for some S ⊂ [N ] with | S| = N/2, we have 1π 1 (S | x) = 1 -2 N | S ∪ S|. We conclude that if E S,a ⋆ J S,a ⋆ (π ⋆ S,a ⋆ ) -J S,a ⋆ ( π) ≤ 1 8 , then E S,a ⋆ | S ∩ S| ≥ 3 8 N . From here, it follows from standard lower bounds for discrete distribution estimation (e.g., Canonne [18] ) that any such estimator S requires n = Ω(N ) samples for a worst-case choice of S. 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 (x 1 , a 1 ), . . . , (x H , a H ) generated by executing π ⋆ in M ⋆ . For each state in each such trajectory, we observe A π ⋆ h (x h , •), whereA π ⋆ h (x, a) = Q π ⋆ h (x, π ⋆ (x)) -Q π ⋆ h (x, a)is the advantage function for π ⋆ .27 • Online setting. The online setting is as follows. There are n at episodes. For each episode i, we execute a policy π i , and receive a "trajectory" o i = (x i 1 , a i 1 , a ⋆,i 1 ), . . . , (x i H , a i H , a ⋆,i H ), where a i h ∼ π i (x i h ) and a ⋆,i h ∼ π ⋆ (x i h ). In addition, for each state in the trajectory, we observe A π ⋆ h (x h , •). After the n episodes conclude, we output a final policy π on which performance is evaluated.Proof of Proposition I.2. We only sketch the proof, as it is quite similar to Proposition I.1. Let N ∈ N be given. We set S = {x, y, z}, A = [N ], and H = 2. We consider a class of problem instances {(M, π ⋆ , r)} indexed by sets S 1 , S 2 ⊂ [N ] with |S 1 | = |S 2 | = N/2 defined as follows. For a given pair (S 1 , S 2 ):• The dynamics are as follows. We have x 1 = x deterministically. If a 1 ∈ S 1 , then x 2 = y, otherwisex 2 = z.• The reward function sets r 1 (x, •) = 0, r 2 (y, •) = 1, and r 2 (z, a) = I{a ∈ S 2 }.• The expert π ⋆ sets π ⋆ (x) = unif(S 1 ), π ⋆ (z) = unif(S 2 ), and π ⋆ (y) = unif([N ])We refer to the problem instance above as I S1,S2 = (M S1,S2 , π ⋆ S1,S2 , r S1,S2 ), and let J S1,S2 (π) denote the expected reward under this instance.Upper bound for online imitation learning with value-based feedback. Consider an algorithm that sets π i 1 = unif([N ]) for each i ∈ [n]. If we play for n = log 2 (δ -1 ) episodes, we will see x 2 = z in at least one episode with probability at least 1δ, at which point we will observe A π ⋆ 2 (z, •). We can pick an arbitrary action with A π ⋆ 2 (z, •) = 0 and return the policy π that sets π 1 (x) = unif([N ]) and π 2 (•) = a; this policy has zero regret.Note that if we define Π = π ⋆ S1,S2 |S1|=|S2|=N/2 as the natural policy class for the family of instances above, then the algorithm above is equivalent to running Aggrevate with the online learning algorithm that, at iteration i, setsπ i h = unif π ∈ Π h | π 2 (z) ∈ arg max a A π ⋆ 2 (x j 2 , a) ∀j < i : x j 2 = z ,For any ∆ ≤ e -1 , this algorithm will terminate after log(1/δ) episodes with probability at least 1δ, and whenever the algorithm terminates, it is clear that π = π ⋆ . In particular, this leads to zero regret for any choice of reward function.Lower bound on offline sample complexity. By setting ∆ ∝ 1 n , an argument essentially identical to the proof of Theorem 2.2 shows that any offline imitation learning algorithm must havemax{E a [J a (π a ) -J a ( π)], E b [J b (π b ) -J b ( π)]} ≳ ∆H ≳ H n .For the sake of avoiding repetition, we omit the details. Finally, we observe that since neither policy in Π takes the action c, Dagger-when equipped with any online learning algorithm that predicts from a mixture of policies in Π, such as in Proposition E.2)-will never take the action c, and hence is subject to the H n lower bound from Theorem 2.2 as well.Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 be 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. 
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 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 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-dependent fashion not captured by existing theory. We identify three phenomena that can lead to improved sample complexity: (i) representational benefits; (ii) value-based feedback; and (iii) exploration.Further directions. Additional directions for future research include (i) developing and analyzing imitation learning algorithms under control-theoretic 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, an important question is to understand whether the notion of supervised learning error D 2 H P π , P π ⋆ we consider is a 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). Low-noiseµ-recoverable Sparse Rewards O R log(|Π|) n O σ 2 π ⋆ log(|Π|) n + R log(|Π|) n N/A Dense Rewards O H log(|Π|) n O σ 2 π ⋆ log(|Π|) n + H log(|Π|) n O µ H log(|Π|) n + H log(|Π|)n 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 Π is the policy class, R is the cumulative reward range, H is the horizon, n is the number of expert trajectories, σ 2 π ⋆ is the variance of the expert policy , and µ is the signed recoverability parameter ; see Section 3 for definitions. 10 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 on horizon, and shows that online interaction, via algorithms like Dagger and Aggrevate, can obtain improved sample complexity under recoverability-type conditions [70, 72, 71, 78] . 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. ( 1)-they 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 is 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 is an active area of research). However, as noted throughout this paper and elsewhere [67] [68] [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 to understand whether limitations of specific algorithms are due to suboptimal design choices versus information-theoretic 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] [68] [69] 80] . Notably, Rajaraman et al. [67] show that when Π is the set of all non-stationary policies in a tabular MDP and R = H, online IL methods can achieve O(µH) sample complexity, while offline IL methods must pay Ω(H 2 ); this is consistent with our findings in Section 2, as log|Π| = Ω(H) for this setting. Other interesting findings from this line of work include the observation that when the MDP dynamics are known, the sample complexity for offline IL with non-stationary tabular policies can be brought down to O(H 3/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 LogLossBC 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 of horizon independence in IL. 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 Π. Various works on theoretical reinforcement learning [2, 33] have observed that finite classes are a useful test case for general function approximation, because they are arguably the simplest type of policy class from a generaliza-tion perspective, yet do not have any additional structure (e.g., linearity) that could lead to spurious conclusions that do not extend to 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-dependent 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] .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 M ⋆ online (without expert feedback), with empirical [1, 109] and theoretical results [81, 83, 82, 16, 20] . This setting encompasses generative adversarial imitation learning and related moment matching methods [42, 57, 49, 79] . 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 is 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-theoretic machinery introduced in Foster and Krishnamurthy [32] and related work [34, 35] , our results are quite specialized to 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-independent 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] . 12These papers provide sample complexity bounds for reinforcement learning that have little or no explicit dependence on horizon whenever rewards are normalized such that H h=1 r h ∈ [0, 1]. We consider a 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/lowrank structure. Nonetheless, our proof of Theorem 3.1 makes use of concentration arguments inspired by Zhang et al. [104, 105] .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-theoretic perspective [88, 41, 61, 14] , and augment behavior cloning with techniques designed to ensure incremental stability (or other control-theoretic 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 (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.Autoregressive language modeling with the standard next-token prediction objective [64] can be viewed as 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 tokens The initial state is x 1 = z ∼ P 0 , where z is a prompt or context. Given the prompt, for each h = 1, . . . , H the action a h ∈ A is a new token, which is concatenated to the state via the deterministic dynamics x h+1 ← (z, a 1:h ). Via Bayes' rule, an expert policyπ ⋆ (a 1:H | z) = H h=1 π ⋆ h (a h | z, a 1:h-1 ) = H h=1 π ⋆ h (a h | x h )can represent an arbitrary conditional distribution over sequences, from which a training setD = {o i } with o i = (z i , a i 1 , . . . , a i H ) is generated. With this setup, log-loss behavior cloning π = arg max π∈Π n i=1 H h=1 log(π h (a i h | z i , a i 1:h-1 ))is equivalent to the standard next-token prediction objective for unsupervised language model pretraining [64] , with the class Π parameterized by a transformer or a similar neural net architecture. In this context, long-range error 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 a fundamental limitation [55, 5] .Applying our results. To apply our results, consider a fixed reward function r = {r h } H h=1 , which might measure performance for a particular task of interest (e.g., question answering or commonsense reasoning). Then, for a model π, J(π) corresponds to rollout performance at the task for an autoregressively generated sequence (i.e., given z ∼ P 0 , we sample a h ∼ π h (• | z, a 1:h-1 ) for all h ∈ [H]). For this setting, Theorem 3.1 states thatEQUATIONwhereσ 2 π ⋆ = H h=1 E π ⋆ (Q π ⋆ h (z, a 1:h ) -V π ⋆ h (z, a 1:h-1 )) 2 .In particular, as long as the cumulative reward for the task is bounded by R = O(1) (e.g., if we receive an episode-level reward r H = 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 D 2 H P π , P π ⋆ . In light of this result, we expect that error amplification observed in practice may arise from challenges in minimizing the generalization error D 2 H P π , P π ⋆ itself (e.g., architecture, data generation process, optimization [17, 13] ), rather than fundamental limits of next-token prediction.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 6 hours.We evaluate the effect of horizon on 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 π ⋆ (which is always a neural network; details below) and construct an offline dataset by rolling out with it n 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 to minimize the LogLossBC 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(π ⋆ ) -J( π) after training, we approximate the average reward of the imitator policy π by selecting new random seeds and collecting n trajectories of length H by rolling out with π; we approximate the average reward of the expert π ⋆ in the same fashion, and we also compute several auxiliary performance measures (details below) that aim to capture the distance between π and π ⋆ . In all environments, we normalize rewards so that the average reward of the expert is at most 1, in order to bring us 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, a classical continuous control task from MuJoCo [86, 85] where the learner attempts to make a stick figure-like 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, a top-down discrete car 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 a sequence of brackets in {{, }, [, ], (, )} and has to 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 (e.g., complexity of the expert policy π ⋆ ), allowing for an honest evaluation of the difficulty of the learning problem as 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 as the horizon increases; this manifests itself in our theoretical results through the realizability condition (Assumption 1.1), which necessitates a more complex function class Π as 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 as 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-Baselines3 [66] implementation of the Proximal Policy Optimization (PPO) algorithm [74] with default settings to train the expert for 500K steps. The policy's action distribution is Gaussian, with the mean and covariance determined by the MLP; 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 as the expert policy, with the 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 ability to generate a valid word is evaluated. We find that regret increases as a 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 log-product-norm acts as a proxy for complexity for the class Π; we rescale such that log-product-norm at H = 10 is 1.0 for both domains. For Dyck, we find that as H increases, the complexity of Π required to represent the expert policy (as measured by the log-product-norm) also increases, explaining the increasing regret in (a). However, the gain in log-product-norm 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-initialized randomly. We train the imitator using the logarithmic loss by default, but as an ablation, we also evaluate the effect of training with the mean-squared-error loss on the Euclidean norm over the actions. We train using the Adam optimizer [53] with a learning rate of 10 -3 and a batch size of 128. We stop training early based on the validation loss on a held out set of expert trajectories. Note that the expert and imitator policies above are both stationary policies.Beamrider. We use the Gymnasium environment BeamRiderNoFrameskip-v4, 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 is a convolutional neural network. We use the same architecture for our imitator policy, with the weights 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 a 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 areM possible lanes. At timestep h ∈ [H + 1], if the agent is in lane i ∈ [M ],then the agent's state is (i, h). We view the state space as a M × (H + 1) grid; a 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, h + 1)), or move one step right ((i, h) → (i + 1, h + 1)). If the agent's action causes it to collide with an obstacle or the boundary of the grid, it is sent to an absorbing state. The agent gets a reward of 1 for reaching the goal state for the first time, and a reward of 0 otherwise. When the agent occupies a state (i, h), it observes an image-based observation x h 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 LogLossBC for autoregressive language generation with transformers (cf. Appendix B.3), where the goal of the "agent" is to complete a valid word of a given length in a Dyck language; this has emerged as a popular sandbox for 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-squared loss (b). The expert policy network is trained on a set of 2 × 10 4 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 a function of H.understanding the nuances of autoregressive text generation in theory [100, 39, 12] and empirically [58, 95] . We recall that a Dyck language Dyck k 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 '()', '[]', and '{}', then '([()]){}' is a valid word, whereas '([)]' and '((({}' are not.Our experiments use the Dyck language Dyck 3 . For our expert, we train an instance of GPT-2 small [64] with 6 layers, 3 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 on an offline dataset of sequences generated by the expert. We assign a reward 1 to each trajectory if the generated word is 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 use parameter sharing via the transformer architecture.We summarize our main findings below.Effect of horizon on regret. Figures 1 and 2 plot the relationship between expected regret and the number of expert trajectories for the Walker2d (MuJoCo), and BeamriderNoFrameskip (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 BeamriderNoFrameskip, we find that increasing the horizon leads to better regret. 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 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. 13Figure 3 (a) plots our findings for the Dyck environment. Here, we see that with the number of trajectories n fixed, regret does increase with H, which might appear to contradict our theory at first 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 2 H P π ⋆ , 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 dependence for Dyck, Figure 3 (b) plots the logarithm of the product of the Frobenius norms of the weight matrices of the expert for varying values of H, as a proxy for supervised learning performance [8, 37] . 14 We find that the log-product-norms do in fact grow with H, consistent with the fact that the regret grows with H 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 as a function of the horizon H, but that this increase in regret can be explained by an increase in the log-product-norm (Figure 3(b) ). However, the effect is mild compared to Dyck.Comparison between log loss and square loss. As an 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 15 ), we find that performance with the MSE loss is comparable to that of the logarithmic loss. For Walker2d, a possible explanation is that under the Gaussian policy parameterization we use, the MSE loss is the same as the logarithmic loss up to state-dependent heteroskedasticity. 16Another 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 2 H P π ⋆ , P π , and (ii) validation loss as proxies for rollout performance. We estimate the Hellinger distance using sample trajectories. Figure 6 displays our findings for Walker2d with H = n = 500, where we observe that both metrics, particularly the Hellinger distance, are well correlated with rollout performance, as 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 as 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, as 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 D 2 H still appears to predict the performance of the policy well, as is consistent with our theoretical results. Lemma D.1 (e.g., Foster et al. [34] ). For any sequence of real-valued random variables (X t ) t≤T adapted to a filtration (F t ) t≤T , it holds that with probability at least 1δ, for all T ′ ≤ T ,T ′ t=1 -log E t-1 e -Xt ≤ T ′ t=1 X t + log(δ -1 ).Lemma D.2 (Time-uniform Freedman-type inequality). Let (X t ) t≤T be a real-valued martingale difference sequence adapted to a filtration (F t ) t≤T . If |X t | ≤ R almost surely, then for any η ∈ (0, 1/R), with probability at least 1δ, for all T ′ ≤ T .T ′ t=1 X t ≤ η T ′ t=1 E t-1 X 2 t + log(δ -1 ) η . Proof of Lemma D.2. Let S t = t s=1 X t and V t = t s=1 E t=1 X 2 t . Let Z t = exp(ηS t -η 2 V t ).As shown in Beygelzimer et al. [11] (see proof of Theorem 1), as long as η ≤ 1/R,E t-1 [exp(ηX t )] ≤ exp(η 2 E t-1 X 2t ), and soE t-1 [Z t ] = E t-1 exp ηX t -η 2 E t-1 X 2 t • Z t-1 ≤ Z t-1 .It follows that (Z t ) is a non-negative supermartingale. Hence, by Ville's inequality, for any η ∈ (0, 1/R), we have that for any τ > 0,P[∃t : S t -ηV t ≥ τ ] = P[∃t : Z t ≥ e ητ ] ≤ e -ητ E[Z T ] ≤ e -ητ .We conclude by setting τ = log(δ -1 )/η.The following result is a standard consequence of Lemma D.2.Lemma D.3. Let (X t ) t≤T be a sequence of random variables adapted to a filtration (F t ) t≤T . If 0 ≤ X t ≤ R almost surely, then with probability at least 1δ, for all T ′ ≤ T ,T ′ t=1 X t ≤ 3 2 T ′ t=1 E t-1 [X t ] + 4R log(2δ -1 ),andT ′ t=1 E t-1 [X t ] ≤ 2 T ′ t=1 X t + 8R log(2δ -1 ).For a pair of probability measures P and Q, we define the total variation distance as D TV (P, Q) = 1 2 |dP -dQ|, and define the χ 2 -divergence byD χ 2 (P ∥ Q) = (dQ-dQ) 2 dQ if P ≪ Q and D χ 2 (P ∥ Q) = +∞ otherwise. We define KL divergence by D KL (P ∥ Q) = dP log dP dQ if P ≪ Q and D KL (P ∥ Q) = +∞ otherwise.The following lemma states some basic inequalities between divergences.Lemma D.4 (e.g., [62] ). The following inequalities hold:• D 2 TV (P, Q) ≤ D 2 H (P, Q) ≤ 2D TV (P, Q). • 1 6 D 2 H (P, Q) ≤ D χ 2 P ∥ 1 2 (P + Q) ≤ D 2 H (P, Q). D.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a 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 to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a 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-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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).• If 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 on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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, or 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS 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 to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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:We use the convention that P0(∅) denotes the initial state distribution.To simplify presentation, we assume that X and A are countable, but our results trivially extend to general spaces with an appropriate measure-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 is to fill this lacuna.For stochastic policies, we overload notation and write f (π(x)) as shorthand for E a∼π(x) [f (a)].While unfamiliar readers might expect a bound on KL divergence, Hellinger distance turns out to be more natural due to a connection to the MGF of the log-loss[89,102]. This facilitates scale-free generalization guarantees in spite of the potential unboundedness of the log-loss. .Complementary to 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.7 In fact, the opposite direction of this inequality holds as well, up to an absolute constant.As discussed at length in Rajaraman et al.[67], many prior works[70,72] state results in a level of generality that allows for stochastic experts, but the notions of supervised learning error found in these works (e.g., TV distance) do not lead to tight rates when instantiated for stochastic experts.An interesting question for future work is to understand if a similar conclusion holds if we replace µ with µ.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.Compared to variance-dependent 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 π ⋆ , whereas these works typically depend on worst-case variance over all policies or similar quantities.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].We only include log-product-norm plots for Dyck and Car because for the other environments (Walker2d and BeamriderNoFrameskip), we do not change the expert as a function of H.In particular, we attempted a similar result in the Atari environment, using MSE loss being between vectors on the probability simplex over |A| 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 was due to numerical instability in optimization for the MSE loss in this setup or a failure of hyperparameter optimization.In theory, the MSE loss can still underperform the logarithmic loss when the heteroskedasticity is severe[32], but this may not manifest for this environment.That is, for all h, I{h = H ⋆ } is a measurable function of (x1, a1), . . . , (x h , a h ).Since π is non-Markovian, we need to expand the state space to x ′ h = x 1:h , a 1:h-1 to apply the performance difference lemma, but since π ⋆ itself is Markovian, this results in the claimed expression.Rajaraman et al.[67] show that for the tabular setting, it is possible to achieve a 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 π ⋆ . Theorem G.1 shows that such a result cannot hold with even constant probability for the same setting. We believe the fact that a 1/n-type rate is even possible in expectation to be an artifact of the tabular setting, and unlikely to hold for general policy classes.We expect that this result extends to improper offline IL algorithms for which π / ∈ Π, but a more complicated construction is required; we leave this for the next version of the paper.These results are 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.As with Proposition I.1, we expect that this lower bound can be extended to improper learners, but a more complicated construction is required.This 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.Our results are not sensitive to whether the learner observes the advantage function or the value function itself; we choose this formulation for concreteness. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - 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)?
- Does online IL algorithm include IRL?
limitations: limitations: - See above.
paper_summary: paper_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$. 

For 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$.

For 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.
strength_weakness: strength_weakness: 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.
2. 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.

References:

[1] Xu et al., Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis, 2023.

[2] Rajamaran et al., Toward the fundamental limits of imitation learning, 2020.
questions: 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: limitations: The authors have adequately discussed and addressed the limitations of this paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The result is intuitive since with "parameter sharing", we assume the policy generalizes to longer horizon states.
- 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?
- 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.
questions: questions: N/A
limitations: limitations: See weakness.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- Some key related work is missing.
questions: questions: **Experiments:**

- 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.
- 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.

**Related Work:**

- [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.

[1] Li, Ziniu, et al. "Rethinking ValueDice: Does it really improve performance?." *arXiv preprint arXiv:2202.02468* (2022).

[2] Xu, Tian, et al. "Understanding adversarial imitation learning in small sample regime: A stage-coupled analysis." *arXiv preprint arXiv:2208.01899* (2022).
limitations: 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.

Comments: title: Following up
Response to Comment
comment: Thanks a lot for the discussion! All of my concerns have been addressed. I have changed my score from 5 to 7.
Dear reviewer,

Thank you for your time! We are following up to check whether our rebuttal has addressed your concerns. Please let us know if you have any further questions.

Thank you,
Authors
Thank you for your interest! We are happy to clarify these points.

### **Regarding comment 1:**
We are happy to include a figure that better explains the distinction between supervised learning and IL in the next version of the paper.

### **Regarding comment 2:**
This is a subtle issue.  One point we should have mentioned earlier is that even though the transitions of the MDP are deterministic, the *initial state is stochastic*, both in MuJoCo and in Atari, which is the default in the Farama Foundation’s Gymnasium.  In this setting, even if every policy is fully deterministic, we expect unnormalized regret to depend on horizon. This is true in theory (in fact, our lower bound for deterministic experts, Theorem 2.2 in our paper, covers exactly this setting) but also intuitively holds true in MuJoCo experiments for the following reason.  Suppose the initial state is drawn so that the learner makes a mistake, leading the walker to fall over; then the reward after the walker has fallen will be zero, even though the expert is able to accrue reward proportional to the horizon by continuing to walk.  To summarize, even when both expert and imitator are deterministic and the MDP has deterministic transitions, as long as the initial state is stochastic, we expect the *unnormalized* regret to scale with the horizon.

### **Regarding GAIL:**
We agree with the reviewer that IRL methods can be beneficial in practice. However, regarding the comment about GAIL specifically, we emphasize that in a minimax sense, the regret *can* be larger than $R / H$, as shown by our Theorem 2.2; indeed, the lower bound in Theorem 2.2 demonstrates that linear scaling with $H$ is necessary for *any algorithm* (information-theoretically) in a worst-case sense when we allow dense rewards (note that in the setting of Theorem 2.2, we have $R/H = 1$). We also remark that GAIL assumes access to a global simulator, allowing the learner to sample trajectories from the MDP according to a given policy, which goes beyond the access model we study for behavior cloning. One interesting takeaway from our work (Theorem 2.2) is the observation that in the worst case, this additional assumption does not lead to improved performance.  However, we emphasize that we agree with the reviewer that IRL methods likely have benefits in practice, and we think that it is an interesting question to better understand the extent to which such improved performance can be proved for some “nice” sub-class of MDPs.
I thank the authors for the detailed response and I would suggest the authors incorporate the above responses in the revised version. Overall, I am maintaining my original score and remain in favor of acceptance.
I appreciate the detailed explanation. I am ready to increase my review score, but I still have some concerns and futher comments are provided below.

**Comment 1:** I clearly understand the response about the 'horizon-free' guarantee. I would like to suggest adding a figure to the paper to clarify the concepts between supervised learning and imitation learning. I also have an additional comment about the reward notion 'R', which I elaborate on below.

**Comment 2:** Could the authors clarify whether the rollout policy for expected regret in Figures 1 and 2 is deterministic or stochastic? I could not find this detail in the Appendix (although I see that the Appendix mentions the expert policy for data collection is deterministic). I ask this because I am conjecturing the following: if the learner's policy is deterministic, the 'unnormalized' regret is also independent of H for the tested environments. This is why I reference the previous work [1] in my review comment. I noticed the authors mentioned using a stochastic policy, but it does not make sense to consider stochastic policies for such tasks.

I want to clarify that I agree the provided empirical results are consistent with the developed theory. However, I am pointing out other possibilities: practitioners usually care about absolute performance, relating to the notions of regret and 'R'. For BC on these tasks, the gap may be independent of the horizon because of deterministic transitions. For the same reason, due to an interest in absolute performance, practitioners also care about adversarial training algorithms like GAIL, which should a gap of $O(1/H * R)$ when using the notion of expected regret, as such methods are observed to achieve good performance regardless of horizon length.
Thank you for the clarification!

Our main results (Theorem 2.1 and Theorem 2.3) are not specialized to log-loss behavior cloning; rather they are reductions that apply to any algorithm that achieves a bound on the trajectory-level Hellinger distance $D_{H}^2(\mathbb{P}^{\hat{\pi}}, \mathbb{P}^{\pi^{\star}})$. For future work, it would be interesting to see if we can design IRL algorithms based on minimizing this quantity. In particular, many existing IRL algorithms can be viewed as performing distribution matching at the occupancy level, but our analysis suggests that performing distribution matching at the trajectory-level might lead to tighter guarantees with respect to horizon.
Thank you for the response.

Regarding IRL, I understand that the lower bound applies to IRL as well, I was more curious about the upper bound. In particular whether the authors have considered using this line of technique to analyze IRL.