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

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

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.

We assume that the reviewer is referring to the fact that our results assume realizability and scale with the complexity of the policy class. We remark:

• Realizability is a standard assumption in RL theory, and is used as a starting point for virtually all existing theoretical results, cf. “Reinforcement learning: Theory and algorithms” (Agarwal, Jiang, Kakade, and Sun).

• Our main results (Theorems 2.1 and 2.3) do not assume that $\Pi$ is well controlled. Rather, these theorems are reductions (in the spirit of prior work on IL) showing that $H$-independent rollout performance is achievable when an appropriate notion of supervised learning error is small. Thus if the policy $\hat{\pi}$ has good supervised learning performance (regardless of whether it belongs to a finite class or enjoys a provable generalization bound), our theorems imply that it will have good rollout performance. Corollaries 2.1 and 2.2 instantiate these results for finite classes for concreteness.

• We note that prior work does not achieve $H$-free guarantees even in the case where $\Pi$ is well controlled. Our results show that with properly normalized rewards, generalization error of $\Pi$ is the only source of $H$ dependence. In some sense, this is the strongest guarantee one might hope for, as the complexity of $\Pi$ influences regret even absent sequential structure in the IL problem. For stationary policies with parameter sharing, our results can be instantiated to give end-to-end guarantees with no dependence on $H$.

• Our most general guarantees for LogLossBC (see Appendix E and Theorem E.1) support infinite policy classes and misspecification, allowing one to trade off policy class complexity with approximation error. The conclusion is the same as for our main results: As long as the supervised learning error (policy class complexity + approximation error) is small, the rollout performance will be horizon-independent.

Some key related work is missing. [2] studied that adversarial imitation learning algorithms can achieve horizon-free sample complexity for structured MDPs. Their results are also important for understanding the horizon in imitation learning.

Thank you for pointing us to this work, which we are happy to discuss in the final version. While [2] contains results concerning $H$-independence, their findings are quite restrictive compared to our paper ( e.g. their notion of horizon independence is not consistent with that in prior work in RL, e.g., Jiang & Agarwal ‘18). Also, their work:

• Is restricted to tabular MDPs and policies (while our work considers general MDPs and function approximation).
• Requires knowledge of the dynamics of the MDP (while our work considers the purely offline imitation learning setting, with no knowledge beyond expert trajectories).
• Only achieves horizon-independence for a restricted class of MDPs called RBAS-MDPs (while our work achieves horizon independence for any MDP, as long as the rewards are appropriately normalized).

While the work of [2] is related and we are happy to cite it, we believe that all claims of novelty and significance of our work stand.

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.

We emphasize that our experiments are intended to validate our theory, particularly the claim that log-loss BC can achieve $H$-independence. We do not claim at any point in the paper that our theory predicts the precise behavior in Figure 1; rather, we claim that Figure 1 validates the theoretical prediction that regret does not degrade as a function of horizon.

Regarding the point about deterministic transitions in MuJoCo and Atari, we emphasize that even if dynamics are deterministic, one can still experience compounding errors due to stochasticity in the learned policy. This phenomenon has been widely observed [11,15, 39].

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.

We believe there may be some confusion here. A key feature of our analysis is that it supports both non-stationary and stationary policies (note that while we use the notation $\pi_h$ throughout the paper, stationary policies are simply a special case in which $\pi_h=\pi$ for all $h$), and we state a number of improved guarantees special to stationary policies, e.g. discussion at the bottom of page 6. If the reviewer has a specific question regarding these results that we can clarify, we would greatly appreciate it.

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.

We believe this summary is misguided; please see the response to question #1.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

The result is intuitive since with "parameter sharing", we assume the policy generalizes to longer horizon states.

While it is certainly intuitive that smaller policy classes yield improved rates, we emphasize that our work is the first to demonstrate that under the assumption of parameter sharing, horizon-free regret is possible with BC in general MDPs; we would like to push back on the idea that it is intuitive that this result holds in such generality, as this finding runs counter to the intuition expressed in many prior works. In particular, one of the key consequences of our work is that under the assumptions of parameter sharing and sparse rewards, the key challenge of compounding error is not present in BC when using Log loss, a finding which we believe is somewhat surprising in light of previous work.

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?

We would like to emphasize that parameter sharing is not actually an “assumption” in our paper, but rather is an important special case of our general results. Indeed, our main results hold in the general case of arbitrary policy classes (Theorems 2.1 and 2.3). Nonetheless, we emphasize that parameter sharing is a natural assumption in practice, and is satisfied whenever the expert policy is stationary with respect to time, which commonly occurs in application domains such as robotics and transformers. Indeed, if parameter sharing does not hold, it means we are training a completely different policy for each step $h$, which is rarely, if ever, done in practice.

We mention in passing that beyond its practical relevance, parameter sharing is a useful special case to isolate the effect that horizon has on offline imitation learning, in the sense that it illustrates the possibility of horizon-free rates.

The experiments are not solid. For example, the Atari figure seems like the Expected regret is random w.r.t. horizon.

Regarding the Atari experiments, we emphasize that Figure 1b and 3b show a a clear trend where the regret with 200 trajectories decreases uniformly as the horizon increases, a demonstration that is amplified by the lack of overlap in the confidence intervals (which is consistent with our theory as we prove that the regret should not increase with horizon). Note that this empirical setup is consistent with our theory, as we have a stationary expert and sparse rewards, and thus expect the regret to be non-increasing with respect to horizon. If the reviewer can clarify why they believe the expected regret is "random" w.r.t. horizon for these experiments, we would greatly appreciate it.

Perhaps the only surprising feature of the Atari experiments is that the regret is actually decreasing with horizon (as opposed to being non-increasing). To understand this, note that our theory provides horizon-agnostic upper bounds independent of the environment. Our lower bounds are constructed for specific worst-case environments, and do not rule out the possibility of improved performance with longer horizons environments with favorable structure. We conjecture that this phenomenon is related to the fact that longer horizons yield fundamentally more data, as the total number of state-action pairs in the expert dataset is equal to nH. In the final version of the paper, we will expand the discussion around this phenomenon, but we would like to emphasize that in no way do our experimental results conflict with the theory established in the rest of the paper.

It is natural to question whether the MuJoCo results really fit the theoretical prediction or simply are due to the task properties.

We are a little confused by this point, but would be more than happy to respond if the reviewer would be willing to further elaborate and clarify why they feel that the MuJoCo results do not fit the theoretical prediction, or explain which task properties they are concerned with.

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

Some formulas and claims in this paper are misleading. In the logarithmic loss of Eq. (5), the policy variable is written as a stationary policy, which does not include the case of non-stationary policies discussed in lines 242-248. Moreover, in Eq. (39) and Eq. (40) in Appendix E.1, the policy becomes non-stationary again, which is inconsistent with Eq. (5). As such, I suggest the authors to write logarithmic losses for stationary policies and non-stationary policies separately.

Our results apply as-is to non-stationary policies. We believe this confusion is caused by a small typo, which is that Eq. (5) (as well as the first equation in App E.1) is intended to be stated with $\log(1/\pi_{h}(a_h | x_h))$, not $\log(1/\pi(a_h | x_h))$. We will be sure to include the _h subscript here and elsewhere in the final version of the paper.

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.

The statement “This bound improves upon the guarantee for indicator loss behavior cloning in Eq.(3) by an O(H) factor” is intended to convey that the bound improves upon Eq. (3) for general policy classes (which is true), not to claim that the bound offers a strict improvement on a per-policy class basis. While the paper already includes extensive discussion around this point (e.g., Page 6), we are happy to change the wording of the statement to make this as clear as possible.

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.

Thank you for pointing us to this work, which we are happy to cite and discuss in the final version of our paper. While the paper [1] does indeed contain some results concerning horizon-independence, their findings are quite restrictive compared to the results in our paper (in particular, unlike our work, their notion of horizon-dependence is not consistent with the standard notion consider in prior work on horizon-independent RL, e.g., Jiang & Agarwal ‘18). In more detail, their work:

• Is restricted to tabular MDPs and policies (while our work considers general MDPs and function approximation).
• Requires knowledge of the dynamics of the MDP (while our work considers the purely offline imitation learning setting, with no knowledge beyond expert trajectories).
• Only achieves horizon-independence for a restricted class of MDPs called RBAS-MDPs (while our work achieves horizon-indepedence for any MDP, as long as the rewards are appropriately normalized). In particular, our notion of horizon-independence is consistent with that considered in Jiang & Agarwal ‘18 and subsequent work.

Thus, while the work of [1] is certainly related and we are happy to cite it, we believe that all claims of novelty and significance of our work stand.

Theorem 2.4 implies that the slow rate for is necessary in both offline and online IL. How can we reconcile this result with the claim in [2] that BC can achieve the rate for stochastic experts in the tabular setting?

This is a great question, which we discuss in Footnote 17. To restate here: Rajaraman et al. [2] show that for the tabular setting, it is possible to achieve a fast $1/n$-type rate in-expectation for stochastic policies. Their result critically exploits the assumption that |X| and |A| are small and finite to argue that it is possible to build an unbiased estimator for the expert policy $\pi^\ast$. Theorem 2.4 shows that such a result cannot hold with even constant probability for the same setting, thereby revealing a separation between the best rate that can be achieved in expectation versus the best rate that can be achieved in probability (note that since the expert is not assumed to be optimal, regret can be negative, which precludes the use of Markov’s inequality to convert an in-expectation bound into a bound in probability).

More broadly, we believe the fact that a 1/n-type rate is even possible in expectation for the tabular setting to be an artifact of the unique structure of this setting, and unlikely to hold for general policy classes or MDPs (e.g., for general policy classes, there is no hope of achieving unbiased estimation).

We thank the reviewer for their positive review and their helpful comments! Please see responses to individual questions below.

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.

This is a great question! Our analysis takes advantage of unique statistical properties of the log-loss (notably, that it provides trajectory-level control over deviations from pi*; see discussion in Sec 2.1.2). In general, other losses do not enjoy similar horizon-independent guarantees (for example, Ross & Bagnell ‘10 show that the indicator loss can have suboptimal horizon dependence, and it is straightforward to see that their counterexample also applies to the square loss and absolute loss). Indeed, one of the key findings of our paper is that using the log-loss is uniquely beneficial.

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)?

No, our results do not assume finiteness of the action space. Our analysis of Log-loss BC can be applied as-is to Gaussian policy parameterizations, as long as the realizability assumption in Assumption 1.1 holds.

Does online IL algorithm include IRL?

The formulation of online IL that we consider assumes that the learner has online/interactive access to both the MDP $M$ and expert $\pi^{\star}$. Typical IRL approaches use a less powerful access model in which we have online access to the MDP $M$ in the same fashion, but do not assume online access to $\pi^{\star}$ itself. Hence, all of the lower bounds for online imitation learning in our paper also apply to IRL.