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

Dylan J. Foster; Adam Block; Dipendra Misra

Source-linked AI summary

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

Dylan J. Foster, Adam Block, Dipendra Misra

arXiv:2407.15007v2Jul 20, 2024cs.LGcs.AImath.STstat.MLstat.TH

TL;DR

Offline imitation learning is widely used, but behavior cloning is associated with unfavorable horizon dependence while online methods require costly expert access. This paper analyzes logarithmic-loss behavior cloning and shows that offline imitation can have horizon-independent sample complexity under controlled payoffs and supervised-learning complexity, narrowing the offline–online gap.

Problem
The paper asks whether the apparent theoretical gap between offline and online imitation learning is fundamental, given offline learning’s practical dominance and online expert access costs.
Source: §1 · pp. 1–2
Method
The paper reduces logarithmic-loss behavior cloning to supervised learning and maximum-likelihood estimation over expert-induced trajectory distributions, then translates learning guarantees into rollout performance.
Source: §2.1 · p. 7
Results
Offline imitation learning can achieve horizon-independent sample complexity under controlled cumulative payoffs and policy-class complexity, with regret largely independent of horizon in two evaluated environments.
Source: §5.2 · p. 18
Takeaways & Limitations
Under standard theoretical assumptions, the gap between offline and online imitation learning is smaller than previously thought, although online methods can still help policy classes without parameter sharing.
Source: §2.4 · p. 9, §6.2 · p. 21
The main analysis focuses on realizable or well-specified settings, while guarantees under misspecification are handled separately in Appendix C.1.
Source: §3 · p. 10

Abstract

from arXiv · show

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 the realizable/well-specified setting with general policy classes up to and including deep neural networks. Through a new analysis of behavior cloning with the logarithmic loss, we show that it is possible to achieve horizon-independent sample complexity in offline 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 smaller than previously thought: (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.

1 Introduction

The paper revisits whether offline imitation learning is fundamentally less sample-efficient than online methods, showing that logarithmic-loss behavior cloning can have horizon-independent or linear-horizon guarantees under suitable conditions. It also establishes limits for online improvements and validates the theory empirically across control and language-generation tasks.

1 Introduction

Imitation learning learns an expert policy from demonstrations without reward feedback or exploration, enabling broad applications but leaving reliability with general neural function approximation unresolved.IL is motivated when specifying rewards is harder than demonstrating behavior, and it often provides more stable training with lower empirical sample complexity than RL.Source: §1 · p. 1

1.1 Background: Offline and Online Imitation Learning

Offline imitation learning uses logged expert trajectories, while behavior cloning reduces the problem to supervised action prediction but appears vulnerable to distribution shift and error amplification.Online methods address this issue by querying the expert on-policy, motivating the paper’s question of whether their apparent sample-efficiency advantage is fundamental.Source: §1 · pp. 1–2

1.1.1 Offline Imitation Learning: Behavior Cloning

Under dense rewards, standard behavior-cloning analyses require Ω(H^2) expert trajectories for constant accuracy because both supervised generalization and rollout error-amplification bounds can be tight.The rollout inequality is tight even for three-state MDPs, while trajectory samples remain dependent despite containing information across H timesteps.Source: §1.1.1 · p. 4

1.1.2 Online Imitation Learning and Recoverability

Online imitation learning avoids error amplification and achieves linear horizon dependence when the recoverability parameter is O(1), although it can match behavior cloning’s quadratic dependence when recoverability is H.Dagger and related methods exploit interactive expert queries to learn corrections on-policy (Ross et al., 2011; Ross and Bagnell, 2014).Source: §1.1.2 · pp. 4–5

1.2 Contributions

LogLossBC achieves horizon-independent offline sample complexity when cumulative payoffs are normalized and supervised-learning complexity is controlled, using trajectory-level information analysis for deterministic and stochastic experts.For deterministic stationary policies with cumulative rewards in [0, H], offline sample complexity can scale linearly with H in arbitrary MDPs, while online IL cannot improve over it without policy-class assumptions.Source: §1.2 · p. 5
For stochastic stationary experts, quadratic horizon dependence is necessary with cumulative rewards in [0, H], but variance-dependent LogLossBC bounds recover linear dependence under a recoverability-like condition.These bounds are the first variance-dependent guarantees for general policy classes and are tight in problem-dependent and minimax senses; online IL still cannot improve without additional policy-class assumptions.Source: §1.2 · pp. 5–6

Experiments.

Experiments on Walker2d, BeamRider, and transformer language generation find imitator performance independent of or improving with horizon, consistent with the predicted LogLossBC behavior.The control experiments cover continuous and discrete action spaces, while language-generation results are largely horizon-independent but more nuanced.Source: Figure 1 · p. 2, §1.2 · p. 6, Experiments · p. 6

1.3 Paper Organization

The paper develops deterministic and stochastic horizon analyses, studies mechanisms beyond horizon dependence, empirically validates them, and concludes with open problems and future directions.The organization separates deterministic results in Section 2, stochastic results in Section 3, mechanisms in Section 4, experiments in Section 5, and open problems in Section 6.Source: §1.3 · p. 6

2 Horizon-Independent Analysis of Log-Loss Behavior Cloning

This section shows that logarithmic-loss behavior cloning can achieve horizon-independent offline imitation-learning guarantees under realizability and controlled supervised-learning complexity. It also establishes when online imitation learning cannot improve these guarantees and explains this through trajectory-level control of errors.

2.1 Log-Loss Behavior Cloning and Supervised Learning Guarantees

LogLossBC estimates the expert’s trajectory law through maximum likelihood, yielding supervised-learning guarantees in squared Hellinger distance for realizable finite policy classes, including stochastic experts.The analysis reduces imitation learning to supervised learning and uses standard maximum-likelihood convergence results.Source: §2.1 · p. 7

2.2 Horizon-Independent Analysis of LogLossBC for Deterministic Experts

For deterministic experts, LogLossBC converts supervised error into horizon-independent rollout guarantees when rewards are normalized and squared Hellinger error is controlled.Squared Hellinger distance enables fast 1/n-type rates and linear horizon dependence, unlike a total-variation reduction.Source: §2.2 · p. 7

2.3 Interpreting the Sample Complexity of LogLossBC

With stationary policies or parameter sharing, LogLossBC achieves horizon-independent sample complexity under sparse rewards and O(H) complexity under dense rewards when log|Π| is controlled.For general policy classes under realizability, the dense-reward result establishes O(H) offline imitation-learning sample complexity.Source: §2.3 · p. 8
For non-stationary policies without parameter sharing, the bound has linear horizon dependence even under sparse rewards, matching the known optimal offline imitation-learning dependence.In tabular MDPs with all non-stationary policies, log|Π| scales with H, and the resulting bound is known to be optimal (Rajaraman et al., 2020).Source: §2.3 · p. 8

2.4 Optimality and Consequences for Online versus Offline Imitation Learning

In dense-reward settings with controlled log|Π|, a lower bound shows that no online algorithm improves Theorem 2.1 uniformly over policy classes, even with recoverability and known dynamics.The lower bound holds for stationary dynamics, rewards, and expert policies, so online and offline imitation learning are equivalent without additional policy-class assumptions.Source: §2.4 · pp. 8–9
Online imitation learning can still improve sample complexity for policy classes without parameter sharing, but offers no improvement for parameter-sharing classes unless µ ≪1.LogLossDagger replaces R with µ for product classes, while parameter-sharing classes retain the offline scaling up to the µ factor.Source: §2.4 · p. 9

2.5 Proving Theorem 2.1: How Does LogLossBC Avoid Error Amplification?

The proof avoids error amplification by measuring trajectory-level deviations, allowing a switch from the learner’s state distribution to the expert’s without spurious horizon factors.Symmetry of the trajectory-level distance and deterministic-expert Hellinger control yield Theorem 2.1; this extends prior work beyond linear parameterized policies to arbitrary parameter-sharing classes and stochastic experts.Source: §2.5 · p. 10

3 Horizon-Independent Analysis of LogLossBC for Stochastic Experts

For stochastic experts, LogLossBC admits a horizon-independent, variance-dependent regret analysis based on supervised learning error. The section shows when horizon dependence reappears, establishes matching lower bounds, and sketches the Hellinger-distance and concentration tools behind the result.

3 Horizon-Independent Analysis of LogLossBC for Stochastic Experts

Theorem 3.1 gives a horizon-independent, variance-dependent regret decomposition for potentially stochastic expert and learned policies.The decomposition is based on supervised learning error D2.Source: §3 · p. 10
Corollary 3.1 shows that stochastic experts generally incur a slow 1/√n rate controlled by expert-policy variance, while σ2_π⋆ = 0 recovers the deterministic bound up to log(n).The stochastic-expert guarantee is obtained by applying Theorem 3.1 to LogLossBC.Source: §3 · pp. 10–11

3.1 Horizon-Independence and Optimality for Stochastic Experts

With R = O(1) and log|Π| = O(1), the cited result is fully horizon-independent, whereas dense-reward settings can require Ω(H²) trajectories, with this quadratic horizon dependence tight.Source: §3.1 · p. 11
A signed recoverability condition restores O(H) sample complexity for dense rewards when eµ = O(1), while online imitation learning cannot uniformly improve offline LogLossBC without further policy-class assumptions.The online lower bound applies even to online algorithms and holds for stochastic experts.Source: §3.1 · p. 12

3.2 Proof Sketch for Theorem 3.1

The proof combines a scale-sensitive Hellinger change-of-measure bound with advantage concentration and a stopping-time truncation that controls trajectory advantages at order R under the expert.The stopping-time step is needed because concentration under the expert does not automatically imply concentration under the learned policy.Source: §3.2 · pp. 12–13

4 Benefits of Online Interaction

Online interaction offers limited horizon-related benefits in realizable imitation learning, but can substantially help through policy-class-dependent representation, value-based feedback, and deliberate exploration. Misspecification introduces unresolved, notion-dependent horizon tradeoffs.

4 Benefits of Online Interaction

Online interaction’s horizon-related benefits are limited, but representational benefits, value-based feedback, and exploration can improve sample complexity in policy-class-dependent ways.The paper expects practical benefits to be problem-dependent and presents these three phenomena as directions for finer-grained theory.Source: §4 · p. 13

4.1 The Role of Misspecification

Under misspecification, horizon dependence varies with the notion of approximation error; detailed tradeoffs with online interaction remain open beyond the realizable, horizon-independent treatment.The authors emphasize that different incomparable misspecification notions produce different horizon dependencies and leave their interplay for future work.Source: §4.1 · p. 13

4.2 Representational Benefits

For H = 2, online imitation learning achieves zero performance gap with probability at least 1 − δ using O(log(δ^-1)) episodes, while proper offline algorithms require n = Ω(N) trajectories.This separation reflects representational benefits unrelated to horizon.Source: §4.2 · p. 14

4.3 Benefits of Value-Based Feedback

Value-based feedback can yield arbitrarily large online improvements: Aggrevate reaches zero gap in O(log(δ^-1)) episodes, while offline feedback or value-free online IL requires n = Ω(N) trajectories.This advantage is representational and cannot be recovered by annotating offline trajectories with expert action-value feedback.Source: §4.3 · p. 14

4.4 Benefits from Exploration

Deliberate exploration can identify the expert in O(log(δ^-1)) episodes with zero gap, while offline IL suffers expected gap Ω(1) · H even when μ = 1.The construction uses a revealing state that the expert never visits; exploration reaches it, whereas offline and naive online methods do not exploit it.Source: §4.4 · p. 15

5 Experiments

Experiments validate the theory across continuous control, Atari, navigation, and autoregressive language generation. Regret is largely horizon-independent when policy complexity is stable, while horizon dependence emerges when the expert class becomes more complex.

5.1 Experimental Setup

The experiments use realizable offline datasets from neural-network experts, matched imitator architectures, varying episode horizons, and reward normalization to keep reward ranges fixed.The suite spans Walker2d, Beamrider, Car, and Dyck, covering continuous and discrete control plus language generation; Dyck experts and imitators are non-stationary transformers.Source: §5.1 · pp. 15, 16, 18

5.2 Results

Across Walker2d and Beamrider, regret remains largely independent of horizons from 50 to 500, with longer horizons improving Beamrider performance.This matches the theory’s horizon-agnostic upper bounds; longer horizons may provide more state-action data, totaling nH pairs.Source: Figure 2 · p. 16, §5.2 · pp. 18–19
Dyck regret increases with horizon because the policy class and supervised-learning error grow as longer valid sequences require more complex experts.The increasing expert log-product norm tracks the increasing regret, despite transformer parameter sharing.Source: Figure 3 · p. 17, §5.2 · p. 19
Car performance degrades only slightly with horizon, consistent with a mild increase in expert log-product norm compared with Dyck.For both logarithmic and mean-squared losses, regret decreases with more expert trajectories but degrades slightly as H increases.Source: Figure 4 · p. 18, §5.2 · p. 19
MSE behavior cloning performs comparably to logarithmic-loss cloning on Walker2d and Car, although MSE failed to train in the Atari experiment.For Walker2d, comparable performance may reflect the Gaussian parameterization, under which MSE matches logarithmic loss up to state-dependent heteroskedasticity.Source: §5.2 · p. 19
Under LogLossBC, Hellinger distance and validation loss correlate strongly with rollout reward, whereas under MSE, Hellinger distance remains reliable but validation loss is weaker.The comparison uses Walker2d with H = n = 500 and evaluates average reward as rollout performance.Source: Figure 6 · p. 20, §5.2 · p. 20

6 Discussion … A.2 Empirical Research on Imitation Learning

The discussion shows that indicator-loss behavior cloning can match logarithmic-loss BC under exact realizability, but is less robust in practice, while broader theory and empirical findings motivate refined, problem-dependent analyses of imitation learning. The related work situates these results against classical online IL, minimax sample-complexity studies, logarithmic-loss benefits, and empirical reports favoring Dagger.

6.1 When is Indicator-Loss Behavior Cloning Suboptimal?

Under deterministic realizability, indicator-loss behavior cloning achieves a horizon-independent rate comparable to LogLossBC under Corollary 2.1’s conditions.This result is presented as novel to the authors’ knowledge.Source: §6.1 · pp. 20–21
Indicator-loss BC is not robust to optimization or misspecification errors, whereas approximate LogLossBC remains horizon-independent and better supports stochastic policies.Indicator-loss error can induce an RH factor in regret, while the logarithmic-loss method degrades only to a bound proportional to R.Source: §6.1 · p. 21

6.2 Conclusion and Future Work

The paper concludes that offline and online IL have a smaller theoretical gap than previously thought, while practical instabilities and online benefits require finer, problem-dependent explanations.Suggested directions include studying exploration and representational benefits of online IL and control-theoretic assumptions capturing practical instability.Source: §6.2 · p. 21
Open questions include whether supervised-learning error D2 adequately proxies real-world performance and how to develop complexity measures characterizing minimax IL sample complexity for general policy classes.The latter should extend ideas analogous to VC dimension or Rademacher complexity to online and offline IL.Source: §6.2 · p. 21

Additional Results

Additional appendix results provide examples and guarantees for LogLossBC and LogLossDagger, plus lower bounds and tightness results for Theorems 2.2 and 3.1.Source: Additional Results · p. 21

A.1 Theory of Imitation Learning and Reinforcement Learning

Classical reductions such as Dagger obtain improved horizon dependence under recoverability assumptions, but prior guarantees often use incomparable supervised-learning notions and lack end-to-end results for specific policy classes.The paper identifies logarithmic loss as beneficial in a minimax decision-making setting, building on but not directly following prior first-order regret analyses.Source: §A.1 · pp. 29–30
Prior minimax analyses often focus on tabular settings, where offline IL can require Ω(H2) versus O(μH) online, while this work establishes horizon independence for general MDPs without known dynamics.The related literature also reports O(H3/2) offline complexity with known dynamics and O(H) under parameter sharing for linear policies.Source: §A.1 · p. 29

A.2 Empirical Research on Imitation Learning

Empirical studies report benefits for Dagger over behavior cloning, but commonly use different losses and do not isolate horizon effects; representational factors may also explain the gains.Other empirical mitigations include data-collection noise injection, inverse reinforcement learning, and control-theoretic stability techniques.Source: §A.2 · pp. 30–31

A.3 Autoregressive Language Modeling … C.1 General Guarantees and Examples for Log-Loss Behavior Cloning

The paper frames autoregressive next-token prediction as logarithmic-loss behavior cloning and derives generalization guarantees through maximum-likelihood analysis, showing that horizon dependence is controlled by policy-class complexity. These results explain when sequence-length-independent rollout performance is possible and identify optimization and generalization, rather than exposure bias itself, as practical bottlenecks.

A.3 Autoregressive Language Modeling

For autoregressive language modeling, next-token prediction is log-loss behavior cloning in a token-level MDP, with prompts as initial states and generated tokens as actions.The policy class may be parameterized by a transformer or similar neural architecture, and the objective matches standard unsupervised language-model pre-training.Source: §A.3 · p. 31
When cumulative reward is bounded by R = O(1), rollout performance has no explicit sequence-length dependence beyond the generalization error D2.For example, an episode-level correctness reward is bounded, so observed error amplification may instead reflect difficulties in architecture, data generation, or optimization (Braverman et al., 2020; Block et al., 2024a).Source: §A.3 · p. 31

Proofs and Supporting Results

The supporting material includes a martingale lemma, definitions of total variation and divergence measures, a proof-included standard result, and a convention using a deterministic dummy initial state.Source: §B.1 · p. 31, §B.2 · p. 32, §B.3 · pp. 32–33

B Technical Tools

The technical appendices establish the concentration, divergence, and variance tools used by the main analysis, including time-uniform Freedman-type inequalities, divergence comparisons, and a law of total variance.These supporting lemmas provide tail bounds, information-theoretic inequalities, and reinforcement-learning variance identities.Source: §B.1 · p. 32, §B.2 · p. 32, §B.3 · p. 33

B.4 Maximum Likelihood Estimation

The MLE appendix analyzes i.i.d. density estimation with log-loss covering numbers and allows optimization error, misspecification, and infinite model classes.Its main proposition supplies the finite-class specialization and identifies the misspecification term as zero when the true density is contained in the class.Source: §B.4 · pp. 33–34

C Examples and Supporting Results from Section 2 and Section 3

The supporting-results overview places general log-loss behavior-cloning guarantees in Appendix C.1 and a log-loss Dagger framework with online guarantees in Appendix C.2.This appendix structure connects the offline bounds to the paper’s broader comparison between offline and online imitation learning.Source: C Examples and Supporting Results from… · p. 35

C.1 General Guarantees and Examples for Log-Loss Behavior Cloning

Log-loss behavior cloning is equivalent to maximum likelihood estimation over the induced density class, enabling guarantees for infinite policy classes, misspecification, and optimization error.The analysis uses a policy covering number and specializes the MLE guarantee to obtain Theorem C.1.Source: §C.1 · pp. 35–36
The general log-loss behavior-cloning bound depends on horizon through the covering-number precision ε/H, yielding at most logarithmic horizon scaling for parametric classes but potentially polynomial scaling for nonparametric classes.The bound also accounts for misspecification, which vanishes when the expert policy belongs to the class.Source: §C.1 · p. 36

C.1.1 Example: Tabular Policies · C.1.2 Example: Softmax Policies

Theorem C.1 yields horizon-independent log-loss behavior-cloning guarantees for stationary tabular policies, while non-stationary tabular policies incur horizon dependence. For softmax policies, covering-number guarantees can give at most polylogarithmic horizon dependence, including stationary linear softmax policies.

C.1.1 Example: Tabular Policies

Stationary tabular policies achieve a generalization bound independent of H when the policy class contains all stationary policies.This applies to both deterministic and stochastic stationary policies through the corresponding complexity controls.Source: §C.1.1 · pp. 36–37
For deterministic stationary tabular policies, the guarantee follows from log|Π| ≤ |X| log|A|.The proof uses the finite policy-class complexity for deterministic policies.Source: §C.1.1 · pp. 36–37
For stochastic stationary tabular policies, the guarantee uses a covering-number bound obtained by discretization.The stated proof appeals to a standard discretization argument, e.g., Wainwright (2019).Source: §C.1.1 · p. 37
Non-stationary tabular policies have sample complexity that scales with H, for both deterministic and stochastic policy classes.The deterministic case has log|Π| ≤ H|X| log|A|, while the stochastic case is controlled through covering numbers.Source: §C.1.1 · p. 37

C.1.2 Example: Softmax Policies

Softmax policy classes induced by value-function classes admit sample-complexity guarantees based on value-function covering numbers.The policy construction uses the softmax map and an ε-cover over value functions.Source: §C.1.2 · p. 37
For softmax policies, the log-loss behavior-cloning guarantee has at most polylogarithmic dependence on H when the value-function class is parametric.If log Nval(F, ε) ∝ log(ε−1), Corollary C.3 yields this horizon dependence.Source: §C.1.2 · pp. 37–38
Stationary linear softmax policies satisfy the parametric covering-number condition when their feature maps are bounded.For feature dimension d and bound ∥ϕh(x, a)∥≤B, the covering complexity scales as d log(Bε−1).Source: §C.1.2 · p. 38

C.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger

This section develops logarithmic-loss DAgger for online imitation learning, providing end-to-end sample-complexity guarantees for general policy classes and supporting both deterministic and stochastic experts. It also instantiates the framework as LogLossDagger and compares its bounds with offline LogLossBC.

General DAgger guarantee

For deterministic experts, DAgger admits a strengthened guarantee, while the analysis also supports stochastic expert policies.The deterministic refinement is obtained through an improved change-of-measure argument.Source: §C.2 · pp. 38–40

Online imitation learning framework

Online IL uses n interactive episodes in which the learner executes policies, queries expert actions along visited trajectories, and outputs a policy with small expert-performance gap.The final policy is uniform over the episode policies.Source: §C.2 · pp. 38–39

Dagger algorithm

The generalized DAgger algorithm uses an online estimator of the expert policy, collects annotated trajectories from the learner’s executions, and guarantees a regret bound for any estimator.The guarantee applies to MDPs characterized by a signed recoverability parameter and uses an online estimation-error notion suited to logarithmic-loss estimation.Source: §C.2 · pp. 38–39

LogLossDagger

LogLossDagger instantiates DAgger with exponential weights and logarithmic loss, yielding a high-probability regret guarantee for finite policy classes containing the expert.The construction applies separately to each layer through the projected classes Π_h.Source: §C.2 · p. 39

Comparison with offline IL

In many parameter regimes, the general DAgger sample-complexity bound is worse than offline LogLossBC, including spurious horizon dependence for stationary policies and a weaker variance-like leading term.The section leaves obtaining the best features of both bounds as an open algorithmic direction.Source: §C.2 · p. 40

D Proofs from Section 2 … E.1.1 Proof of Lemma E.2 (Regret Decomposition for Stopped Advantages)

The proofs establish structural properties of the trajectory-wise policy distance, a hard online imitation-learning instance, and a stopped-advantage decomposition that supports Theorem 3.1. Together, they connect policy distance, regret, and change-of-measure arguments under bounded stopped advantages.

D.1 Proof of Theorem 2.1

The trajectory-wise distance ρ(· ∥·) is symmetric, bounds reward differences, and is equivalent to Hellinger distance up to constants when one policy is deterministic.These results establish the metric properties used in Theorem 2.1.Source: Proof of Theorem 2.1 · p. 41

Proof of Theorem 2.1.

Theorem 2.1 follows by rewriting trajectory expectations and applying the policy-distance bounds to compare rewards under stochastic and deterministic policies.The proof uses indicator-based trajectory expansions and the deterministic-policy structure to relate the distance to Hellinger quantities.Source: Proof of Theorem 2.1 · pp. 42–43

D.2 Proof of Theorem 2.2

The lower-bound construction for Theorem 2.2 uses two self-looping states, two constant policies, and two reward instances that are optimal for different experts.The instances differ only on the low-probability initial state, while the policy distance satisfies ρ(πa, πb) = H.Source: Proof of Theorem 2.2 · p. 44

Proof of Theorem 2.2.

A Le Cam two-point argument shows that online learners cannot reliably distinguish the two instances because informative feedback occurs only when the initial state is y.The proof bounds total variation through the rarity of x1 = y, yielding the claimed hard-instance conclusion.Source: Proof of Theorem 2.2 · p. 44

E.1 Proof of Theorem 3.1

For Theorem 3.1, the proof defines cumulative advantages and stops at H⋆ when their magnitude exceeds L, making H⋆ a stopping time with |∆H⋆(o)| ≤ L + 1.The stopping rule keeps the stopped advantage bounded for the subsequent change-of-measure argument.Source: §E.1 · p. 45
Theorem 3.1 then combines the stopped-advantage regret decomposition with Hellinger change of measure, stopped-martingale moment bounds, and a final application of Lemma 3.2.The proof separately controls the first and second moments under the expert and learner policies before choosing parameters to conclude the theorem.Source: §E.1 · p. 45

E.1.1 Proof of Lemma E.2 (Regret Decomposition for Stopped Advantages)

Lemma E.2 constructs a non-Markovian policy that follows the learner until H⋆ and the expert afterward, then applies the performance difference lemma to decompose regret at the stopping time.Measurability of the stopping event ensures the constructed policy is well defined and permits the required filtration-based identities.Source: §E.1.1 · pp. 47–48
The remaining terms in Lemma E.2 are bounded by conditioning on the stopping events {H⋆ = h} and using that the constructed policy agrees with the learner before stopping.Auxiliary Lemmas E.5 and E.6 supply the bounds needed to combine the stopped and unstopped contributions.Source: §E.1.1 · pp. 47–49

E.1.2 Proof of Lemma 3.2 (Concentration for Advantages) … Proof of Proposition 4.1.

The appendix proves concentration for advantages, establishes an online imitation-learning lower bound through a reward-free construction, and supplies additional proofs. It also proves Proposition 4.1 by contrasting online identification with an offline sample lower bound.

E.1.2 Proof of Lemma 3.2 (Concentration for Advantages)

Lemma 3.2 adapts Zhang et al. (2021, 2022) to arbitrary, potentially suboptimal policies, assuming normalized rewards and bounded Q- and V-values.The proof combines filtration-based concentration, Jensen’s inequality, auxiliary lemmas, union bounds, and telescoping arguments to obtain the stated high-probability bound.Source: §E.1.2 · pp. 49, 51, 52

E.2 Proof of Theorem 3.2

The online proof permits action selection from observed sequences, thereby encompassing offline imitation learning as a special case.It fixes H, n, σ^2, K, and Δ before defining the hard MDP and policy class.Source: §E.2 · p. 52, Proof of Theorem 3.2 · p. 52

Proof of Theorem 3.2

The construction specifies a reward-free MDP with deterministic dynamics, two actions, and two experts, and considers four expert–reward instances altogether.Source: Proof of Theorem 3.2 · p. 52
The construction sets Δ² = c · K/(Hn) with c sufficiently small, ensuring TV(Pa, Pb) ≤ 1/2 and a probability bound of at least 1/8 on one of four problem instances.The parameter is finally set to K = σ²/H.Source: Proof of Theorem 3.2 · p. 54

E.3 Additional Proofs

The additional proofs derive Proposition 3.1 using Jensen’s inequality and Lemma B.5.The supplied passage provides the proof’s key inequality steps but not the proposition’s full statement.Source: §E.3 · p. 54

F.1 Proof of Proposition 4.1

For Proposition 4.1, the constructed two-step family hides the expert’s action a⋆ offline while online exploration can reveal it after visiting state z.The family indexes instances by a subset S and a⋆, with transitions determined by whether the first action lies in S.Source: §F.1 · p. 55, Proof of Proposition 4.1 · p. 55

Proof of Proposition 4.1

Online imitation learning identifies a⋆ after observing z with n = log2(δ^-1) episodes and can then return a zero-regret policy.The construction is equivalent to DAgger with an online learner that updates after encountering z.Source: Proof of Proposition 4.1 · p. 55
Offline imitation learning requires n = Ω(N) samples in the worst case because trajectories never visit z, leaving a⋆ unidentifiable and requiring estimation of S.The lower bound follows from standard discrete distribution-estimation bounds such as Canonne (2020).Source: Proof of Proposition 4.1 · p. 55

F.2 Background and Proof for Proposition 4.2

The section defines offline and online imitation learning with value-based feedback, then proves matching linear-sample lower bounds for offline learning and an online upper bound using targeted exploration. It also sketches that online learning without value-based feedback requires linear samples in the worst case.

Background on value-based feedback

Offline feedback provides expert advantages at states from n expert trajectories, whereas online feedback collects trajectories and expert feedback while executing n learner policies.The online learner outputs a final policy after the episodes conclude.Source: §F.2 · p. 56

Upper bound for online imitation learning with value-based feedback

With value-based feedback, randomizing the first action reveals the informative state z within log2(δ−1) episodes with probability at least 1−δ, enabling a zero-regret policy.The construction uses states {x,y,z}, actions [N], horizon H=2, and expert action sets S1,S2 of size N/2.Source: §F.2 · p. 56

Lower bound for offline imitation learning

Offline learning requires n=Ω(N) samples in the worst case because expert trajectories never visit z, leaving S2 unidentifiable and requiring discrete-distribution estimation.The lower-bound construction yields reward based on selecting actions in S2 at z, but the offline data distribution does not depend on S2.Source: §F.2 · p. 56

Lower bound for online imitation learning without value-based feedback

Without value-based feedback, any online algorithm guaranteeing sufficiently small regret on all instances can be converted into estimators of S1 and S2, requiring n=Ω(N) samples in the worst case.The argument is analogous to the offline lower bound and holds with constant probability for a sufficiently small absolute constant c.Source: §F.2 · pp. 56–57

F.3 Proof of Proposition 4.3 · G Additional Lower Bounds

The proof constructs two indistinguishable problem instances where a simple online strategy identifies the expert quickly, while offline learning and restricted online mixtures retain an H^n lower bound. Additional appendices extend lower bounds to active online learning, stochastic experts, and per-policy tightness.

F.3 Proof of Proposition 4.3

The construction uses three states and three actions: actions a and b self-loop at x, while c transitions to terminal state z; y and z are terminal.Source: §F.3 · p. 57
Two problem instances share the dynamics but assign different expert policies and rewards, with each expert optimal and reward parameter µ = 1.Source: §F.3 · p. 57
An online algorithm tests action c after observing initial state x, identifies the expert from its action at z, and returns the corresponding policy.Source: §F.3 · p. 57
With probability at least 1 − δ, the online algorithm terminates after log(1/δ) episodes for ∆≤e−1 and then achieves zero regret for any reward function.Source: §F.3 · p. 57
Despite this online result, an argument paralleling Theorem 2.2 gives an H^n lower bound for any offline imitation-learning algorithm.Source: §F.3 · p. 57
Dagger also suffers the H^n lower bound when its online learner predicts only from mixtures of policies in Π, because neither policy takes action c.Source: §F.3 · p. 57

G Additional Lower Bounds

Appendix G.1 shows that Theorem G.1’s lower-bound conclusion persists for online imitation learning under an active sample-complexity framework.Source: G Additional Lower Bounds · p. 58
Appendices G.2 and G.3 provide an instance-dependent lower bound for stochastic experts and examine the per-policy tightness of Theorems 2.1 and 3.1.Source: G Additional Lower Bounds · p. 58

G.1 Lower Bounds for Online Imitation Learning in Active Interaction Model

This section shows that allowing online imitation learners to query experts selectively does not generally improve over LogLossBC beyond a logarithmic factor. The lower bound holds for stationary dynamics, rewards, and deterministic experts in a simple reward-free MDP family.

Active sample complexity

The active framework counts only episodes in which the learner queries the expert, with M := Pn i=1 M_i and M ≤ n, rather than counting every online episode.The learner may decide at any step whether to query the expert, and an episode contributes one query to M if any query occurs.Source: §G.1 · p. 58

Lower bound

Theorem G.1 constructs a reward-free MDP with |X| = |A| = m + 1, policy class satisfying log|Π| = log(m), and deterministic rewards and experts, where any algorithm with E[M] ≤ c·m suffers a lower-bounded expected suboptimality.The construction applies for any m ∈N and H ∈N, with an absolute constant c > 0.Source: §G.1 · p. 58

Hard-instance construction

The hard instance uses m self-looping terminal states, uniformly initialized, and pairs each candidate deterministic expert with a reward function for which that expert is optimal and µ = 1.All dynamics, rewards, and expert policies in the theorem are stationary.Source: §G.1 · pp. 58–59

Lower bound

Because log|Π| = log(M), active online interaction can improve the LogLossBC sample-complexity bound by no more than a log(n) factor.The comparison treats the LogLossBC bound from Theorem 2.1 as using M = n.Source: §G.1 · p. 58

G.2 An Instance-Dependent Lower Bound for Stochastic Experts

The section establishes an instance-dependent lower bound for offline imitation learning with stochastic experts. In autoregressive MDPs, a local minimax construction shows that the leading term of LogLossBC’s guarantee is essentially unimprovable without additional assumptions.

Lower-bound optimality

Theorem 3.2 shows qualitatively that the leading-order term in Theorem 3.1 is optimal for stochastic experts across a suitable class of MDPs.This indicates that substantial improvement requires assumptions beyond those used for the LogLossBC guarantee.Source: §G.2 · p. 60

Local minimax construction

For any expert policy and reward function in an autoregressive MDP, there is an alternative policy yielding a local minimax regret lower bound over two rewards and two expert policies.The proof uses a Le Cam two-point argument and tensorization of Hellinger distance to make the alternatives statistically difficult to distinguish.Source: §G.2 · pp. 60–61

Implication for LogLossBC

Theorem G.2 implies that the leading term in Theorem 3.1 cannot be substantially improved on a nearly per-instance basis, in the regime where that term dominates the lower-order term.The theorem fixes a bounded reward function and expert policy, then constructs an alternative policy for every sample size n.Source: §G.2 · p. 60

Proof mechanism

The construction relies on the equivalence between stochastic policies in autoregressive MDPs and arbitrary joint laws over action sequences.This equivalence connects policy construction to distributions whose expected bounded payoff differs while remaining difficult to distinguish from offline data.Source: §G.2 · p. 61

G.3 Tightness of the Hellinger Distance Reduction

Theorem G.3 establishes a converse showing that the Hellinger-distance reductions can be tight for arbitrary policy pairs and reward-free MDPs, using suitably constructed non-Markovian rewards. Tightness holds under bounded-range or bounded-variance conditions, while the result leaves possible per-MDP improvements when states do not encode full history.

Converse result

Theorem G.3 shows that, for any policy pair and reward-free MDP, a non-Markovian reward can make the reductions in Theorems 2.1 and 3.1 tight.The construction can make each term in Eq. (18) tight and also make Theorem 2.1 tight.Source: §G.3 · p. 63

Assumptions and limitations

The tightness construction requires rewards depending on full histories, although this is without loss of generality when the MDP state already contains that history.For MDPs lacking this property, the theorem leaves open whether the reductions can be improved on a per-MDP basis.Source: §G.3 · p. 63

Tightness regimes

Bounded-range rewards can make Theorem 2.1 and the lower-order term in Eq. (18) tight, whereas bounded-variance rewards can make the leading term in Eq. (18) tight.The bounded-variance construction need not have bounded range.Source: §G.3 · p. 63