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

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.

Strengths

- This paper presents extensive theoretical results for offline IL and online IL under the general function approximation class. It builds a sharp separation between offline and online algorithms, which the reviewer appreciates a lot. - The reviewer believes that the analysis tools in this paper can be further applied in future studies of imitation learning and sequential decision making.

Weaknesses

- The theoretical results have a gap with practice. For example, the reviewer finds it odd that the conclusion of a 'horizon-free' guarantee is obtained by assuming the policy class is well-controlled. Practitioners often choose a large function class to ensure the approximation error is small. - Some key related work is missing.

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

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

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.

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.

Strengths

- The theory to further understand the complexity of BC is important. - The presentation is clear and easy to follow.

Weaknesses

- The result is intuitive since with "parameter sharing", we assume the policy generalizes to longer horizon states. - 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

N/A

Rating

4

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

See weakness.

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.

Strengths

1. This paper provides a new understanding of the horizon dependence in IL. Classical IL works show that the offline IL method BC suffers a quadratic horizon dependence, motivating various online IL approaches that attain improved linear horizon dependence. However, this paper proves that in certain cases, it is possible for BC to achieve linear horizon dependence and online IL cannot improve over offline IL, suggesting that there is no fundamental gap between offline IL and online IL. 2. This paper contributes new techniques for analyzing IL methods, which could be of independent interest. To attain a linear horizon dependence for BC, this paper presents a sharp horizon-independent regret decomposition. For deterministic experts, this regret decomposition is based on a novel trajectory-level analysis. For stochastic experts, they provide an interesting information-theoretic analysis. I believe that these new techniques could inspire further advancements in IL theory.

Weaknesses

1. Some formulas and claims in this paper are misleading. In the logarithmic loss of Eq. (5), the policy variable $\pi (a^i_h|s^i_h)$ is written as a stationary policy, which does not include the case of non-stationary policies $\Pi = \Pi_1 \times \Pi_2 \times \cdots \times \Pi_H$ discussed in lines 242-248. Moreover, in Eq. (39) and Eq. (40) in Appendix E.1, the policy becomes non-stationary again, which is inconsistent with Eq. (5). As such, I suggest the authors to write logarithmic losses for stationary policies and non-stationary policies separately. Furthermore, in line 224, they claim that “This bound improves upon the guarantee for indicator loss behavior cloning in Eq.(3) by an O(H) factor”. This statement is a little problematic since the bound in Corollary 2.1 does **not** improve upon previous bounds for the case of non-stationary policies. 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

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?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have adequately discussed and addressed the limitations of this 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.

Strengths

- As far as I know this is the first approach that leverages Hellinger distance on analyzing imitation learning methods. - The paper extends the BC results to stochastic policies under other function classes. - Interesting that online IL cannot really improve upon offline IL without further assumptions. - In addition to the theory the appendix provides experimentation that supports the theory. - The paper is very well written---I enjoyed reading the paper.

Weaknesses

- The paper only considers log loss, which I understand is very commonly used, but I am curious about how much of these analyses transfer to other losses.

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?

Rating

9

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

- See above.