PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Dylan J. Foster, Adam Block, Dipendra Misra

arXiv:2407.15007v2cs.LGcs.AImath.STstat.MLstat.TH

TL;DR

The paper revisits whether offline imitation learning is fundamentally worse than online learning because of horizon dependence and costly expert access. It analyzes logarithmic-loss behavior cloning and finds that the offline–online gap is smaller under standard theoretical assumptions, with horizon-agnostic empirical regret in tested environments.

  • Problem

    Offline imitation learning remains dominant because online expert access can be costly or infeasible, despite theory suggesting online methods improve horizon dependence.

  • Method

    The paper studies behavior cloning as supervised prediction and analyzes logarithmic loss using policy-class-dependent supervised-learning complexity.

  • Results

    Regret was largely independent of horizon in Walker2d and BeamriderNoFrameskip, while the offline–online gap was smaller than previously thought under standard theoretical assumptions.

  • Takeaways & Limitations

    Online imitation learning does not universally improve over offline behavior cloning; its benefits remain policy-class dependent, especially when policies lack parameter sharing across steps.

  • Takeaways & Limitations

    In an Atari experiment, behavior cloning with MSE loss failed to improve even with 500 expert trajectories, possibly because of optimization instability or unsuccessful hyperparameter tuning.

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 online imitation learning is fundamentally more sample-efficient than offline behavior cloning, showing that logarithmic-loss behavior cloning can substantially reduce or remove horizon dependence under controlled payoff range and policy-class complexity. For deterministic stationary policies, offline learning can match linear-horizon online guarantees, while online access offers advantages mainly for policy classes without parameter sharing or under practical effects not captured by standard theory.

  • Offline behavior cloning: Classical behavior cloning reduces imitation learning to supervised prediction but can incur quadratic horizon dependence because supervised error is amplified across sequential decisions.The paper notes that both the supervised generalization bound and the horizon amplification argument can be tight in general.
  • Horizon-independent analysis: Logarithmic-loss behavior cloning can achieve horizon-independent offline sample complexity when cumulative payoffs and supervised-learning complexity are controlled.A trajectory-level information-theoretic analysis supports both deterministic and stochastic experts.
  • Deterministic policies: Under dense rewards, offline behavior cloning achieves linear horizon dependence for deterministic stationary or parameter-sharing policies in arbitrary MDPs.This matches the dependence previously known for online imitation learning.
  • Deterministic policies: Without further policy-class assumptions, online imitation learning cannot improve over offline logarithmic-loss behavior cloning, even in benign MDPs.Online methods can still help non-stationary policies without parameter sharing.
  • Stochastic policies: For stochastic stationary experts, quadratic horizon dependence can be necessary under dense rewards, but variance-dependent analysis enables linear dependence under a recoverability-like condition.The paper presents these bounds as tight in a problem-dependent sense for general policy classes.
  • Empirical and broader implications: Experiments on MuJoCo, Atari, and autoregressive language generation support the theoretical picture while highlighting practical instabilities and horizon-dependent supervised-learning effects.The conclusion distinguishes these practical phenomena from the smaller offline–online gap predicted under standard theoretical assumptions.

2 Horizon-Independent Analysis of Log-Loss Behavior Cloning

LogLossBC reduces offline imitation learning to supervised maximum-likelihood estimation and can translate controlled log-loss error into horizon-independent rollout guarantees. For deterministic experts, this closes much of the offline–online gap: dense rewards permit linear horizon dependence offline, while online improvement depends on policy-class structure.

  • 2.1 Log-Loss Behavior Cloning and Supervised Learning Guarantees: LogLossBC estimates the expert trajectory law through maximum likelihood, then translates its supervised learning guarantee into rollout performance.The analysis applies to realizable policy classes and extends beyond finite classes under misspecification.
  • 2.2 Horizon-Independent Analysis of LogLossBC for Deterministic Experts: Horizon-independent rollout bounds follow when cumulative rewards are normalized and supervised log-loss error is controlled.The proof uses trajectory-level control and squared Hellinger distance rather than total variation, enabling fast 1/n-type rates.
  • 2.3 Interpreting the Sample Complexity of LogLossBC: For stationary or parameter-sharing policies, LogLossBC achieves horizon-independent sample complexity with sparse rewards and linear horizon dependence with dense rewards.When log|Π| = O(1), sparse rewards have R = O(1), while dense rewards have R = O(H).
  • 2.4 Optimality and Consequences for Online versus Offline Imitation Learning: Even with online access, recoverability, and known dynamics, no algorithm uniformly improves on the offline guarantee over all policy classes.The lower bound applies in dense-reward settings with controlled policy-class complexity.
  • 2.4 Optimality and Consequences for Online versus Offline Imitation Learning: Online imitation learning improves over offline LogLossBC for policy classes without parameter sharing, but not generally for parameter-sharing classes unless recoverability is especially favorable.The refined online bound replaces R with µ, whereas parameter sharing yields a bound that does not improve over offline learning unless µ ≪1.
  • 2.5 Proving Theorem 2.1: How Does LogLossBC Avoid Error Amplification?: Trajectory-level distance lets the analysis switch from the learned policy’s state distribution to the expert’s without error amplification or spurious horizon factors.This symmetry is the key proof step behind the deterministic regret decomposition.

3 Horizon-Independent Analysis of LogLossBC for Stochastic Experts

For stochastic experts, LogLossBC yields horizon-independent, variance-dependent regret decompositions rather than deterministic experts’ fast rates. The resulting bounds are tight: dense rewards can require quadratic horizon dependence, while sparse rewards remain horizon-independent under parameter sharing.

  • 3.1 Horizon-Independent Regret Decomposition: LogLossBC gives a horizon-independent and variance-dependent regret decomposition for potentially stochastic experts.The analysis uses a change-of-measure argument for Hellinger distance and supervised log-loss guarantees.
  • 3.1 Horizon-Independent Regret Decomposition: Stochastic experts generally incur a slow 1/√n rate, while zero expert variance recovers the deterministic bound up to a log(n) factor.The slow term is controlled by the expert-policy variance.
  • 3.2 Horizon Dependence for Stochastic Experts: With parameter sharing and sparse rewards, the stochastic-expert guarantee has no explicit horizon dependence.A law-of-total-variance argument prevents the variance term from scaling with horizon when R = O(1).
  • 3.2 Horizon Dependence for Stochastic Experts: With dense rewards, stochastic experts can require Ω(H^2) trajectories even when log|Π| = O(1), unlike deterministic experts, for which O(H) samples suffice.The lower bound establishes that the quadratic dependence is tight in general.
  • 3.3 Consequences for Online versus Offline IL: Online imitation learning cannot uniformly improve over offline imitation learning for stochastic experts without additional policy-class assumptions such as no parameter sharing.This conclusion follows from a lower bound applying to both online and offline algorithms.
  • 3.4 Proof Strategy: The stochastic analysis is necessary because trajectory-wise distance no longer vanishes when comparing a stochastic expert with itself.This necessitates a more information-theoretic treatment than the deterministic trajectory-level argument.

4 Benefits of Online Interaction

Online interaction offers benefits beyond horizon dependence, but these benefits are limited for stationary policy classes and depend on the policy class or feedback available. The paper identifies representational benefits, value-based feedback, and exploration as distinct mechanisms.

  • Overview: For stationary policy classes, recoverability has limited horizon-related benefits, although online interaction may still help through representation, value feedback, or exploration.The authors expect practical online benefits to be problem-dependent and present these mechanisms as directions for a more fine-grained theory.
  • Scope and Limitations: The analysis focuses on the realizable setting, while the tradeoff between misspecification and horizon dependence remains open for future work.The paper notes that different notions of misspecification can produce different horizon dependence and leaves their interaction with offline versus online IL unresolved.
  • Representational Benefits: Online IL can outperform offline IL for representational reasons even when horizon is constant, rather than because of recoverability.For H = 2, an online algorithm can achieve zero imitation gap with O(log(δ^-1)) episodes, while proper offline methods require Ω(N) trajectories.
  • Value-Based Feedback: Value-based feedback can yield arbitrarily large representational gains online, but annotated offline trajectories or online methods without such feedback cannot achieve the same improvement.The informal proposition gives O(log(δ^-1)) online episodes with value-based feedback versus an Ω(N) trajectory requirement for the comparison settings.

5 Experiments

Experiments across control, Atari, car-racing, and language-generation tasks test how LogLossBC regret changes with horizon, trajectory count, policy complexity, and loss choice. Regret is largely horizon-independent when task complexity is stable, while horizon-dependent degradation appears when the policy class must become more complex.

  • Horizon dependence: Regret is largely independent of horizon in Walker2d and Beamrider, consistent with the theoretical prediction.The evaluation varies H from 50 to 500; Beamrider sometimes improves as horizon increases.
  • Horizon dependence: Longer horizons provide nH expert state-action pairs, which may offset horizon-related regret growth in tasks whose complexity remains stable.The authors conjecture that the additional data from longer trajectories helps explain the observed scaling.
  • Task complexity: Dyck regret increases with horizon because the policy complexity required to represent the expert also grows, as reflected by increasing log-product norms.The log-product norm is used as a proxy for supervised-learning complexity, linking the rising complexity to rising regret.
  • Task complexity: Car shows only mild horizon-related regret degradation, consistent with its smaller increase in log-product norm compared with Dyck.The authors attribute the mild scaling to a milder growth in the complexity proxy.
  • Loss comparison: MSE and logarithmic loss achieve comparable performance in Walker2d and Car, although MSE training failed to improve performance in the Atari setup.The Walker2d similarity may follow from the Gaussian policy parameterization, while the Atari issue is attributed to numerical instability or unsuccessful hyperparameter optimization.
  • Performance proxies: Hellinger distance is a strong rollout-performance proxy under LogLossBC, whereas validation loss is less reliable under MSE.For Walker2d, Hellinger distance and validation loss correlate strongly with reward under LogLossBC; under MSE, validation loss can remain similar across policies with different expected rewards.

6 Discussion

The discussion argues that offline and online imitation learning have a smaller theoretical gap than previously thought, while identifying practical phenomena and complexity measures that remain insufficiently explained.

  • 6.1 When is Indicator-Loss Behavior Cloning Suboptimal?: Indicator-loss behavior cloning achieves a horizon-independent rate for deterministic realizable policies, but this result is not robust to optimization or misspecification errors.Approximate indicator-loss optimization can restore an H-dependent regret term, whereas logarithmic-loss behavior cloning degrades more gently under approximate optimization.
  • 6 Discussion: Offline IL can match favorable horizon dependence under standard realizable assumptions, narrowing the theoretical gap with online IL.The paper reports horizon-independent or linear-horizon offline guarantees in settings previously associated mainly with online methods.
  • 6.2 Conclusion and Future Work: The paper identifies a need for finer, problem-dependent theories covering exploration, representational benefits, practical instability, language models, and general policy classes.An open question is to develop complexity measures analogous to VC dimension or Rademacher complexity for online and offline IL.
  • Related work: Prior offline and online analyses often reduce imitation performance to different supervised-learning quantities, limiting direct comparison and concrete end-to-end guarantees for rich policy classes.This makes it difficult to distinguish algorithmic design limitations from information-theoretic limitations, especially for neural networks.
  • Related work: The analysis is specialized to imitation learning and does not directly follow from existing information-theoretic results, despite using related machinery.The paper also notes that its supervised-learning error measure may not be a suitable proxy for real-world performance in all settings.

A.3 Autoregressive Language Modeling

Autoregressive language modeling can be viewed as behavior cloning with logarithmic loss, making sequence generation an imitation-learning instance. Under bounded cumulative reward, the paper’s guarantee removes explicit sequence-length dependence except through supervised generalization error.

  • A.3 Autoregressive Language Modeling: Standard next-token prediction is equivalent to logarithmic-loss behavior cloning in a token-level MDP with transformer-like policy classes.Prompts are initial states, tokens are actions, and generated prefixes define subsequent states.
  • A.3 Autoregressive Language Modeling: The theoretical application evaluates a model by sampling an autoregressive sequence under a fixed task reward and identifying its rollout performance with J(π).The policy samples each token conditionally on the prompt and preceding tokens.
  • A.3 Autoregressive Language Modeling: For bounded cumulative reward R = O(1), rollout performance has no explicit dependence on sequence length apart from the generalization error D2.An episode-level correctness reward is given as an example of a bounded cumulative payoff.
  • A.3 Autoregressive Language Modeling: The result suggests that observed long-range error amplification may arise from difficulty minimizing generalization error rather than from a fundamental next-token-prediction limit.The paper connects this interpretation to practical challenges involving architecture, data generation, and optimization.

C.1.1 Example: Tabular Policies

For tabular policy classes, logarithmic-loss behavior cloning yields horizon-independent guarantees for stationary policies, while non-stationary classes retain horizon dependence. Parametric function classes can achieve only polylogarithmic horizon dependence through their covering complexity.

  • C.1.1 Example: Tabular Policies: Stationary tabular policies yield a behavior-cloning sample-complexity bound independent of horizon H.This holds for deterministic stationary policies and is also extended to stochastic stationary policies.
  • C.1.1 Example: Tabular Policies: Non-stationary tabular policies retain sample-complexity dependence on H under logarithmic-loss behavior cloning.Separate corollaries cover deterministic and stochastic non-stationary policy classes.
  • C.1.1 Example: Tabular Policies: For general policy classes, horizon dependence enters through evaluating the covering number at precision ε/H, producing at most logarithmic dependence for parametric classes but potentially polynomial dependence for nonparametric classes.The paper leaves optimal horizon dependence for nonparametric classes open.
  • C.1.1 Example: Tabular Policies: Stationary linear softmax policies provide a function-approximation example with a generalization guarantee derived from value-function covering numbers.The covering complexity scales with the feature dimension and the ratio Bε^-1.

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

The online framework lets the learner execute policies, query expert actions, and update an estimator across episodes. Log-loss Dagger provides general regret guarantees, but its rates can be worse than offline logarithmic-loss behavior cloning in some parameter regimes.

  • C.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger: Online imitation learning proceeds over episodes in which the learner executes a policy, observes expert annotations, and uses accumulated data to produce a final policy.The general Dagger framework is parameterized by an online learning algorithm that estimates the expert sequentially.
  • C.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger: Dagger’s regret is controlled by a signed recoverability parameter and an online estimation-error term for arbitrary online estimators.A separate guarantee is provided for deterministic experts.
  • C.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger: LogLossDagger instantiates Dagger with exponential weights and logarithmic loss, yielding finite-class regret guarantees under realizability.The construction operates layer by layer using projections of the policy class.
  • C.2 Online IL Framework and Sample Complexity Bounds for Log-Loss Dagger: For many parameter regimes, the general online Dagger bound is worse than the offline LogLossBC bound, including spurious horizon dependence for stationary policies.The online result also has a weaker variance-like leading-order quantity in the cited comparison.

D Proofs from Section 2

The proofs establish trajectory-wise policy-distance properties, connect this distance to reward differences, and use stopped-advantage and change-of-measure arguments to complete the main theorem.

  • Trajectory-wise distance: The trajectory-wise distance ρ(· ∥·) is symmetric, so the asymmetric definition yields a valid semi-metric.This is shown for potentially stochastic policies.
  • Trajectory-wise distance: Reward differences between policies can be bounded using the trajectory-wise distance ρ(· ∥·).For deterministic experts, this distance is also related to Hellinger distance through Lemmas D.1 and D.3.
  • Lower-bound proof: The lower-bound construction uses self-looping states and two expert policies to make the relevant feedback distributions difficult to distinguish.A Le Cam two-point argument is applied after bounding the total variation distance between observations.
  • Theorem proof: The main argument combines concentration bounds, moment control, and change of measure before rearranging the resulting inequality to prove the theorem.The proof uses Lemma 3.2 after controlling first and second moments under the expert and comparison policy.
  • Stopped advantages: The proof controls cumulative advantages with a stopping time, ensuring the stopped sum is bounded and enabling a strong change-of-measure argument.The stopping time is measurable and yields |∆H⋆(o)| ≤ L + 1 almost surely.

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

The concentration proof adapts existing arguments to arbitrary, potentially suboptimal policies and combines uniform-in-horizon bounds with a hard offline-learning construction.

  • Concentration argument: The concentration lemma requires non-trivial modifications of prior arguments because the evaluated policy may be arbitrary and suboptimal.The proof assumes rewards and value functions are bounded after normalizing R = 1.
  • Concentration argument: The proof combines martingale, telescoping, union-bound, and moment arguments to obtain a high-probability bound simultaneously for all H′ ∈ [H].The resulting statement holds with probability at least 1 − 5δ.
  • Hard instance: The construction extends to multiple reward and expert-policy combinations, while the learner’s observation law remains independent of the reward function.This indistinguishability supports the subsequent total-variation lower bound.
  • Hard instance: The lower-bound proof chooses ∆ so that total variation remains bounded and concludes that at least one instance forces substantial error with constant probability.The parameter choice sets ∆^2 proportional to K/(Hn).

F.2 Background and Proof for Proposition 4.2

This section defines offline and online value-based feedback and proves that offline imitation can require linearly many samples in the action-space size, while online feedback can reveal the hidden target quickly.

  • Feedback models: Offline learning observes expert trajectories and value-based feedback, whereas online learning executes candidate policies and receives trajectories containing expert actions and value information.After the episodes, the learner outputs a final policy whose performance is evaluated.
  • Offline lower bound: The lower-bound instance uses a first-step subset S1 to determine whether the trajectory reaches y or z, with rewards at z depending on a second hidden subset S2.The expert selects uniformly from S1 at x and from S2 at z.
  • Online upper bound: With online value-based feedback, observing z reveals the needed value information and permits a zero-regret policy after n = log2(δ^-1) episodes with probability at least 1 − δ.The resulting policy sets the first-step action uniformly and chooses the appropriate second-step action.
  • Offline lower bound: For offline imitation, trajectories never visit one state, so the expert’s action there is unidentifiable and estimating the relevant action subset requires n = Ω(N) samples.The lower bound follows from standard discrete-distribution estimation arguments.
  • Feedback models: The formulation is insensitive to whether the learner observes an advantage function or the value function itself.The paper chooses the advantage-function formulation for concreteness.

F.3 Proof of Proposition 4.3

The proof constructs an online intervention that reveals the expert’s hidden action and contrasts it with an offline lower bound, showing that restricted policy classes can prevent Dagger from exploiting the intervention.

  • Hard instance: The MDP contains a special action c that transitions from x to z, while actions a and b leave x self-looping and y and z are terminal.This action structure creates an informative state that the experts themselves never visit.
  • Online procedure: An online learner can take c, observe the expert’s action at z, and return the matching policy, achieving zero regret after log(1/δ) episodes with probability at least 1 − δ.The procedure returns πa or πb according to the observed expert action.
  • Offline comparison: The corresponding offline learner cannot access the informative state and inherits the H/n lower bound from Theorem 2.2.The proof states that any offline imitation-learning algorithm must satisfy this lower bound.
  • Offline comparison: Dagger with any online learner that predicts only from mixtures of policies in Π also never takes c, so it remains subject to the same H/n lower bound.Neither policy in Π selects the intervention action.
  • Additional results: The appendix additionally gives active-sample, stochastic-expert, and per-policy tightness results, including a local minimax lower bound for autoregressive MDPs.These results complement the main lower bounds and examine their tightness.

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

The active framework lets learners choose when to query expert feedback, but its lower bound still limits the benefit of online interaction. For deterministic experts, this limitation holds in a constructed reward-free MDP even with stationary dynamics and rewards.

  • Active interaction model: The learner may query the expert at any step of an episode, and feedback is available only when it makes such a query.This framework is more permissive than requiring expert feedback in every episode.
  • Active interaction model: Active sample complexity counts episodes in which the learner queries the expert at least once, rather than all online interaction episodes.The total number of queries is M := ∑_{i=1}^n M_i, where M_i indicates whether episode i includes an expert query.
  • Lower-bound theorem: With expected active sample complexity E[M] ≤ c·m, any online algorithm faces a deterministic-expert instance with a lower-bounded expected suboptimality.The construction uses a reward-free MDP, m+1 states and actions, m+1 reward functions, and a policy class with log|Π| = log(m).
  • Implication: Online interaction improves over LogLossBC by at most a log(n) factor in this example, so active querying does not remove the lower-bound barrier.The example sets log|Π| = log(M) and applies the Theorem 2.1 bound with M = n.
  • Hard-instance construction: The hard instances use self-looping terminal states with uniform initialization and policies that differ at one designated state.Each instance has an optimal deterministic expert, and all instances satisfy μ = 1.

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

This section studies whether the stochastic-expert guarantee for offline imitation learning can be improved on individual instances. In autoregressive MDPs, a local minimax construction shows that the leading-order guarantee is qualitatively optimal without additional assumptions.

  • Implication: The result shows that the leading term in Theorem 3.1 cannot be substantially improved on a nearly per-instance basis without additional assumptions.The conclusion concerns stochastic experts and the special autoregressive-MDP setting.
  • Local minimax lower bound: Theorem G.2 constructs, for any expert policy and reward function, an alternative policy yielding a per-instance lower bound for offline imitation learning.The alternative policy is evaluated in an autoregressive MDP with rewards bounded by R.
  • Regime of tightness: The lower bound applies once n ≥ c′ · R^2σ^2, matching the regime where the leading σ^2/n term dominates the lower-order term.The stated sample-size restriction is described as natural for the theorem’s leading-order regime.
  • Proof strategy: The proof uses a two-point argument, Hellinger-distance tensorization, and a technical perturbation lemma to make expert and alternative-policy datasets difficult to distinguish.The construction exploits the equivalence between stochastic policies in the autoregressive MDP and joint laws over action sequences.

G.3 Tightness of the Hellinger Distance Reduction

The Hellinger-distance reductions underlying Theorems 2.1 and 3.1 are tight under suitable reward constructions. The converse results establish this for bounded-range and bounded-variance regimes, while non-Markovian rewards limit the generality of the claim.

  • Converse results: For any pair of policies and reward-free MDP, reward functions can make the reductions in Theorems 2.1 and 3.1 tight.The converse theorem covers potentially stochastic learned and expert policies.
  • Scope condition: The tightness construction requires non-Markovian rewards whose value functions depend on the full history.The reward at time h may depend on x1:h and a1:h.
  • Tightness regimes: Bounded-range rewards can make Theorem 2.1 and the lower-order term of Theorem 3.1 tight, while bounded-variance rewards can make Theorem 3.1’s leading term tight.The bounded-variance construction does not necessarily have bounded range.
  • Scope condition: When the state already contains the full history, the non-Markovian-reward assumption is without loss of generality; otherwise, per-MDP improvement remains open.Thus the converse is strongest for MDPs whose states encode prior history.
Loading 2407.15007v2…