Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
They propose a reply estimation way that uses a combination of simulated and empirical rollouts to optimally estimate expert moments. They show the finite sample guarantee that can enjoy both of the worlds of BC and moment matching. 
strengths_and_weaknesses: This paper's result is arguably strong. But at the same time, I feel some of the results are currently hard to understand. Many details are in the appendix currently, and hard to tell what are real assumptions and caveats from the main text.  

(Strengths) 

* Their proposed algorithm is sufficiently novel as far as I know.  
 
* Their theoretical results are also very interesting. At least, I didn't expect we can enjoy both of the worlds of BC and moment matching in the function approximation setting. 

(Weakness) 
It looks like many important stuff are in the appendix. I can understand it might be due to the page constraint. The presentation would be much more improved by cutting some of the stuff. 

* I personally feel Section 2 is too long? I guess it is introduced for readers to get some intuition. But, personally, I cannot get so much good intuition from these special instances, figure 2 and figure 3. (other reviewers might feel in a different way though) I would like to suggest authors shorten this section (just introduce BC/moment matching/replace estimation and what are known results in the tabular setting) without introducing these special instances. 

* Some of the theorems are written in expectation. Some of the theorems are written in high probability.  This is confusing since comparisons would be not apple to apple sometimes.  Could you try to be consistent? If the authors cannot,  that’s fine. But, could you explain why? 

* Some assumptions of theorems are hidden in the appendix. I think they should be in the main text as much as possible. (I think this can be done by shortening section 2 a lot) 

	* For example, in Theorem 3.1, “instantiated with an appropriate discriminator F”… This should be in the man text. And It should be explained if it is not trivial stuff. 
	* Theorem 2.  Did you assume the realizability of the reward function? But then, assumptions are stronger than BC? In this sense, you cannot directly compare with BC since the assumptions are different?  Does the same stuff apply to moment matching since moment matching might not require the reazaibility of the policy class? 
	* Assumption 2 sounds strong. I am not sure you can really claim this result handles general function approximation. It looks like it only holds in the simple parametric case. How about more complete classes such as neural networks or random forests? (If not, “function approximation with parametric models” sounds more reasonable as a tile of the paragraph) 
	* Theorem 3:“Appropriately instantiating —-“ This should be in the main text. 
	* Line 321: “Whenever we are able to establish —- up to ‘’: How reasonable it is? When does it happen/ 



	


questions: I wrote down the question above. 
limitations: Not applied.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the imitation learning problem with general function approximation. The authors utilized the replay estimation (RE) technique to improve the moment matching (MM) method. To analyze RE with general function approximation, they first introduced the membership oracle M and proved a general performance guarantee as a function of M. Then they instantiated the membership oracle with an offline classification oracle and proved a meta-theorem under some assumptions on this offline classification oracle. Based on this result, they argued that when the parameter error matches the generalization error (i.e., $\mathcal{E} _ {\Theta, n, \delta} \asymp \mathcal{E}_{\Theta, n, \delta}^{\text {class}}$), the imitation gap of RE is better than that of MM. Finally, they showed the empirical performance of RE on some tasks.
strengths_and_weaknesses: Strengths:
1. This paper conducts a rigorous theoretical study for online imitation learning with general function approximation. To handle the challenge brought by function approximation, the author introduced the membership oracle, which is novel in imitation learning literature.
2. To instantiate the membership oracle, they proposed an offline classification oracle that can achieve a small statistical error for parameter estimation. With this offline classification oracle, they proved a performance guarantee for the resultant algorithm, which contributes new analysis.  


Weakness:

1. The idea of replay estimation is not novel in imitation learning. In the tabular and known transition setting, [1] leverages the transition function to obtain a better estimation of the expert’s moments. Furthermore, [2] extends this idea to the setting where the transition function is unknown but environment interactions are allowed. In [2], they employ BC’s policy to interact with the environment and utilize the collected trajectories to establish a better estimation. This is exactly the replay estimation technique used in this paper. However, the discussion about the relation to the existing work [2] is missing in this work.

2. Due to the first point, the main contribution of this paper is that they applied the replay estimation technique with general function approximation. However, in the setting of general function approximation, the proposed algorithm and analysis require access to a strong offline classification oracle (assumption 2). This offline classification oracle is required to have a small parameter estimation error. Note that this parameter estimation error does not consider the data distribution, in stark contrast to the generalization error used in supervised learning. Therefore, this offline classification oracle asks a much stronger requirement than learning a classifier with a small generalization error in supervised learning. Besides, the RE method is proved to have a better imitation gap than MM only when the parameter error matches the generalization error. However, the key question of when the parameter error matches the generalization error is not answered in this paper.        

     
3. For the experiment part, I have the following two concerns.

   a). In experiments, the classical moment matching method has poor performance while BC enjoys superior performance. This observation largely conflicts with the well-accepted empirical observation that moment matching based methods can match expert’s performance even with few expert trajectories on locomotion tasks [3, 4, 5]. Besides, in [6], they evaluated a similar MM approach named AdIRL on locomotion tasks from the same Py-Bullet suite. They showed that AdIRL can match expert’s performance across all environments, which conflicts with the experimental observation in this paper. This contradiction raises a doubt about whether the MM method is implemented correctly in experiments.
   
   b). Besides, as far as I am concerned, the performance gap established in this paper cannot explain the superior performance of RE in experiments. As the bound $\min (H^{3 / 2} / N_{\exp }, H / \sqrt{N_{\exp }} )$ suggests, RE has a better performance gap than MM in the large data regime $N_{\exp} \succsim H $. Nevertheless, in experiments, they considered the low data regime where $H \approx 1000$ and $N_{\exp} \leq 20$. Therefore, I believe that the developed theory cannot explain the experimental results in this paper.


4. Some theoretical results in this paper have been established in the existing work [2]. In particular, for moment matching, the performance gap upper bound and a tight lower bound (Theorems 3.1 and 3.2) have been proved in [2]; see Theorem 1 and Proposition 2 in [2] for details. However, the discussion on [2] is missing in this work.

References:

[1]. Rajaraman, N., Yang, L. F., Jiao, J., and Ramachandran, K. Toward the fundamental limits of imitation learning. arXiv preprint arXiv:2009.05990, 2020.

[2]. T. Xu, Z. Li, and Y. Yu. On generalization of adversarial imitation learning and beyond. arXiv, 2106.10424, 2021.

[3] J. Ho and S. Ermon, “Generative adversarial imitation learning,” in Advances in Neural Information Processing Systems 29, 2016, pp. 4565–4573.

[4] I. Kostrikov, K. K. Agrawal, D. Dwibedi, S. Levine, and J. Tompson, “Discriminator-actor-critic: Addressing sample inefficiency and reward bias in adversarial imitation learning,” in Proceedings of the 7th International Conference on Learning Representations, 2019.

[5] K. Brantley, W. Sun, and M. Henaff, “Disagreement-regularized imitation learning,” in Proceedings of the 8th International Conference on Learning Representations, 2020.

[6] G. Swamy, S. Choudhury, J. A. Bagnell, and S. Wu, “Of moments and matching: A game-theoretic framework for closing the imitation gap,” in Proceeding of the 38th International Conference on Machine Learning, 2021, pp.10 022–10032.

questions: 1. In lines 56-57, the authors argued that they achieved the best-known imitation gap under significantly weaker assumptions compared with the prior work [Rajaraman et al. (2021a)]. In my opinion, these two works impose two different types of assumptions and it is hard to say which one is weaker. Can the authors elaborate more on this point?

2. In eq.(6), it seems to be $P (s _ { 1 \cdots t-1 }) \rightarrow P (s _ { 1 \cdots t })$ since we should also consider the weight on $s_t$ for estimating the moment in time step $t$?

3. The weak margin condition in assumption 3 is hard to understand. Can the authors explain more about the meaning of this condition and why this condition is required in the analysis? 

limitations: The authors discussed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of online imitation where the environment interaction is allowed. This paper focuses on the moment matching method. The vanilla method directly estimates the expert's state-action distribution and therefore suffers a sample barrier issue when the sample size is sufficiently large. To address this issue, this paper extends the idea presented in Rajaraman et al. (2020) with new algorithm designs and analyses. Specifically, the proposed algorithm in this paper can work with function approximation, whereas the MIMIC-MD algorithm in Rajaraman et al. (2020) is only applied to the tabular setting. In terms of the theoretical analysis, this paper shows an imitation gap $\widetilde{O}(H^{3/2} d^{5/4}/N_{\exp})$ in the linear function approximation setting, under weaker assumptions compared with that in Rajaraman et al. (2021a). Finally, experiments on tasks from the PyBullet suite show the efficacy of the proposed algorithm.

=====

After the rebuttal, most of my concerns are well addressed. I recommend accepting this paper for two reasons. First, it makes a significant step in improving the worst-case bound of MM-style algorithms. Second, it investigates an interesting experiment setup. The main criticism of this paper includes insufficient related work (refer to the Limitations section) and weak experiment results (refer to my last reply on the discussion page). Based on the assumption that the authors can fix all these issues before the final version, I recommend accepting this paper and increase my score from 5 to 7. 

 
strengths_and_weaknesses: **Strengths**

- This paper introduces several new algorithm designs (soft membership and prefix weight). These components make the idea in Rajaraman et al. (2020)  more generable.
- This paper provides new and better theoretical guarantees for the proposed algorithm. These theoretical results are essential for studying the minimax optimality on a statistical side.

**Weakness**

- Some relevant references are missing. The discussion in Section 2 has been presented in the prior work; see [1]. The idea of learning a BC policy and rolling out it to collect more trajectories to improve the estimation is also considered in [1]. The theoretical analysis of MM (Theorem 3.1 and Theorem 3.2 in this paper) has been conducted in [1]. Prior studies [2-4] about MM (and variants) are not even mentioned. 
- Gaps between theory and practice. This paper studies the worst-case bound of RE. But, it is not clear for which kind of instances and what kind of setting, RE can be better than other algorithms. Though this paper presents some numerical results to answer such questions, these results are not very convincing. Please refer to the detailed comments below. 

[1] T. Xu, Z. Li, Y. Yu, and Z.-Q. Luo. On generalization of adversarial imitation learning and beyond. arXiv, 2106.10424, 2022.

[2] Z. Liu, Y. Zhang, Z. Fu, Z. Yang, and Z. Wang. Provably efficient generative adversarial imitation learning for online and offline setting with linear function approximation. arXiv, 2108.08765, 2021b.

[3] Xu, T., Li, Z., & Yu, Y. (2020). Error bounds of imitating policies and environments. *Advances in Neural Information Processing Systems*, *33*, 15737-15749.

[4] Y. Wang, T. Liu, Z. Yang, X. Li, Z. Wang, and T. Zhao. On computation and generalization of generative adversarial imitation learning. In Proceedings of the 8th International Conference on Learning Representations, 2020.
questions: 
- Can the authors help explain why MM has different algorithm behaviors in Figure 2 and Figure 3?

 This paper claims that MM might fail on the MDP shown in Figure 2, but later on, it says that it can take the green action (expert action) on the MDP shown in Figure 3. However, the theoretical guarantee in Theorem 3.1 for MM cannot tell me why MM is sometimes good and sometimes bad. I realize algorithm properties of MM are much studied in the prior work [1]. Are there new insights in this paper? 

- Why is the performance of MM bad on Pybullet Env? Is the superior performance of RE really benefited from a better estimation?

I observe that the performance of MM is bad in Figure 5, and I am surprised by this result because I believe that MM should perform well. To support my thought, I conducted an experiment by running the DAC algorithm without any tunning (the experiment configuration follows the code given by the authors). DAC is a particular case of MM when the function class allows a KL-divergence to measure the state-action distribution matching. Then, I find that with 10 expert trajectories, DAC can achieve the performance of 1500 ($\pm 500$) on HopperBulletEnv and 2000 ($\pm 200$) on Walker2dBulletEnv. I believe further tuning can boost the performance. 

The main concern is when can RE be better than MM? MM-style algorithms are known to perform well on many tasks, even though it may suffer a sample barrier issue in the worst case. The authors are recommended for the discussion in Section 3.3 of [1], in which it is shown that RE has no clear advantage over MM in instances similar to locomotion control. 
limitations: I appreciate and like the theoretical results developed in this paper. However, I still have some concerns. 

**Important references are missing**

I believe the current references are somehow biased. I would suggest that the authors add a section of related work, if the authors agree. For example, similar instances in Figure 2 and Figure 3 and associated upper bound and lower bound for MM have been studied in [1]. Furthermore, the idea of RE (i.e., learning a BC policy to rollout) is also presented in [1] (though [1] studied the tabular setting). I think the connection with [1] should be clarified. It would be great to give credits for prior studies of MM algorithms (in other papers, it is called adversarial imitation learning algorithms) [2, 3, 4]. Otherwise, readers cannot give a full picture of MM algorithms. 



**Gaps Between Theory and Practice**

- It is not clear for what kind of instances RE is better.  Note that we cannot claim that an algorithm is better than another if the upper bound is better.  This is because upper bounds could be loose. Even for instances in Figure 2 and Figure 3 of this paper, I do not know whether RE can be better than BC or MM, since there are no experiments or theoretical guarantees. Compared with the lower bound instances for BC and MM, I know RE can show an advantage in the large sample regime. But I do not know whether these hard cases occur in practice (or at least, whether these hard instances are similar to tasks in the benchmark considered in this paper). 
- The improvement of RE is in the large sample regime but the experiment is in a small sample regime. From Figure 4, it seems that MM is better in a large sample regime ($N_{\exp} > |S|H$). However, the improvement magnitude should be minor in this regime, as the imitation gap of MM is already smaller than $\mathcal{O}(\sqrt{H})$. To better see this, let us consider the locomotion control tasks, in which H=1000. Then, the imitation gap of MM is smaller than 31, meaning that the improvement of a better algorithm can not be larger than 31. However, in experiments, it is shown that RE can be significantly better than MM in a small sample regime. 
- MM should have good performance. This paper shows that MM has bad performance on Walekr2dBulletEnv. Though I do not find a good reference from the literature, my experiments show that MM can perform well; refer to my comments in the Questions section.

I would suggest that this paper can be rephrased to emphasize the theoretical contributions, if the authors agree. The motivation in section 2 in terms of ''better than both worlds'' is not very sound to me (the authors are encouraged to explain more about this motivation). Instead, I believe that a study of minimax optimality is sufficient to motivate this paper. 

**Minor Issues**

- A right bracket is missing in Line 15 of the abstract.

- The MM family is too large and it is not clear which algorithm is studied in the main paper. In Appendix, it seems that TV distance is considered. I believe this point should be clarified in the main paper.  It is recommended to give more explanations about MM (though I prefer the name of state-action distribution matching). Otherwise, it is hard to follow the discussion in Section 2.

- The sample regime in theoretical guarantees should be clarified. For example, the bound in Theorem 3.1 should be $\min \\{ H, H\sqrt{|\mathcal{S}|/N_{\exp}} \\}$. Otherwise, one may be confused that if $N_{\exp}= 1$, the theoretical guarantee in Theorem 3.1 is meaningless. In other words, the bound in Theorem 3.1 is only meaningful in a large sample regime where $N_{\exp} > |\mathcal{S}|$.

- In experiments, this paper claims that gradient penalty can improve the convergence rate. But, I do not realize this point. Instead, I know that the gradient penalty can help reduce the generalization error; see the discussion about the discriminator in [3-4].


I would like to recommend accepting this paper if the above concerns are well addressed. Basically, some misleading claims should be clarified.
review_title: null

Meta-review: metareview: Everyone in the review committee see this as a strong paper with a novel and practically useful replay estimation technique. Solid theoretical contribution with a meta theorem that can deal with general function approximation and weaker assumptions. Also strong empirical results on various benchmark. During rebuttal, authors were able to address most of the technical comments. Great work!
confidence: Certain
Decision: Accept