Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation

Summary

This paper analyses the AIL problem in the context of general function approximation. Specifically, authors propose an algorithm which is both sample efficient and computationally efficient. Finally, the paper concludes with an empirical validation of the results.

Strengths

- The paper analyses the AIL problem with general function approximation, which is interesting - Author focus on both theoretical guarantees and practical implementation - Authors validate the results empirically

Weaknesses

- There are many typos. For instance: - line 12 "near-expert" - line 43 you say have extended, but [28] is older than [54] - table 1 it should be "linear mixture" - line 141 $\mathcal{R}_h$ does not represent a reward class defined in that way - line 143,149 it should be "realizability" - line 145 $\mathcal{Q}_h$ does not represent a class defined in that way - line 190 I think that the value functions should have an hat - ... - The authors make many assumptions to solve the problem. In particular, assumptions 1,2,3, as well as assumption 4, which I am not sure how strong it is as structural assumption - Algorithm 1 requires to keep in memory all the K policies collected so far, which are many according to Theorem 1. Thus, this stuff may be rather inefficient concerning the memory storage.

Questions

- why your algorithm has an expert complexity which does not depend, differently from other algorithms, on the state-action space someway? - At lines 246-248, when you say that your algorithm improves by an order of $\mathcal{O}(H^2)$ over BC, why do you think is so? Because of the structural assumptions that you added to the problem? Moreover, I do not understand why the rate of BC is $H^4$ instead of the common $H^2$. - at lines 324-325, you say that a promising direction would be to try to achieve the optimal $H^{3/2}/\epsilon$ rate for the expert sample complexity. But who says that this is the optimal rate for the general function approximation setting? Authors [35] demonstrate that $H^{3/2}/\epsilon$ is optimal in the tabular setting thanks to accurate estimates of the transition model. But if you look at [34], authors say that the knowledge of the transition model does not allow to break the quadratic barrier in problems with continuous state space trivially, but have to devise something else. What do you think?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors have adequately addressed the limitations and potential negative societal impact of their work.

Summary

This paper introduces optimization-based adversarial imitation learning (OPT-AIL), a novel method for online AIL with general function approximation. OPT-AIL combines online optimization for rewards and optimism-regularized Bellman error minimization for Q-value functions. Theoretically, it achieves polynomial expert sample complexity and interaction complexity, marking it as the first efficient AIL method with general function approximation. Practically, OPT-AIL simplifies implementation by requiring the optimization of only two objectives. Empirical results show OPT-AIL outperforms previous state-of-the-art deep AIL methods.

Strengths

- This paper introduces OPT-AIL, a novel approach that addresses both theoretical and practical limitations of existing AIL methods by utilizing general function approximation. - This paper provides both thoeretical and empirical results to validate the proposed algorithm. - The error decomposition is new and provides a new point for understanding AIL.

Weaknesses

- The complexity measure and main idea of algorithm is not entirely novel, which is based on GEC and a series of optimism-based work on general function approximation like GOLF. - It seems that the paper mainly focus on the value-based hypothesis class and cannot incorporate the model-based ones directly. - The discussions on errors $\varepsilon_{\rm opt}^r$ and $\varepsilon_{\rm opt}^Q$ is not sufficient (see Questions).

Questions

- It is mentioned that one of the motivations of focusing on general function approximation is the implementation of neural networks in practice. How can neural network function class be included in the architecture? What’s the complexity of such classes? - In the 3rd line of OPT-AIL, a no-regret algorithm is implemented to obtain the reward. Though author provides some explanations, it's still remain a bit confusing to me. Can authors elaborate more on this part, e.g., algorithm, optimization target, a brief recap of theoretical analysis (if these topics are well-dicussed in literature)?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

I suggest the authors to include more dicussions on the primary techincal difficulties in contribution part while deriving their theoretical results for AIL.

Summary

This paper studies adversarial imitation learning (AIL). From a theoretical perspective, it proposes a new algorithm OPT-AIL which works in the context of general function approximations, accompanied with a provable sample efficiency guarantee. The advantage of the proposed theoretical algorithm is that it can be easily adapted to a practical version based on neural network implementations.

Strengths

**Orginality and Significance:** 1. The proposed algorithm is the first provably sample efficient online AIL under general function approximations, which is an important contribution to the theoretical understanding of imitation learning. 2. The proposed algorithm features an optimism-regularized Bellman-error minimization subproblem which makes the algorithm both provably sample efficient (for the online setup) and amenable to practical implementations based on neural networks. 3. Experimental results demonstrate the effectiveness of the proposed algorithm. **Quality and Clarity:** The presentation is quite clear. The theoretical results are sound and are well proved.

Weaknesses

1. The idea and techniques in this paper seems direct given the existing theoretical works on AIL and RL with general function approximations especially [1] and [2]. 2. The assumption of low generalized eluder coefficient [2] is from standard RL literature and is directly adapted here, without further explanations or discussions. **References:** [1] Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. *Advances in Neural Information Processing Systems 36*, 2024. [2] Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. *arXiv*, 2211.01962, 2022.

Questions

1. When the main theory translates to linear (or linear mixture) setups in AIL, how does the corresponding result compare with the previous arts? 2. Could the authors highlight the theoretical difficulties or novelties that arise from applying the idea of [1] to the setup of AIL?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Please see the weakness section and the question section above.

Summary

This paper explores the theory of adversarial imitation learning (AIL) using general function approximation. The authors introduce a novel approach called Optimization-Based AIL (OPT-AIL). OPT-AIL employs a no-regret subroutine for optimizing rewards and minimizes the optimism-regularized Bellman error for Q-value functions. The authors prove that OPT-AIL achieves polynomial expert sample complexity and interaction complexity, effectively imitating the expert. They also implement a practical version of OPT-AIL, demonstrating that it outperforms existing baseline methods across various environments.

Strengths

1. Originality: This paper introduces the first provably efficient algorithm for adversarial imitation learning (AIL) with general function approximation. 2. Solid Mathematics: While I did not verify the proofs in the appendix, the algorithm appears standard, suggesting the proofs should be correct. 3. Good Writing: The paper is well-written, and the motivation is clear from the introduction and related work sections. Readers can easily understand the algorithm from sec 4.1 and the pseudo code. 4. Good Experimental Results: The practical version of OPT-AIL outperforms standard AIL baselines in various environments.

Weaknesses

1. The practical algorithm itself is not highly innovative. The idea of running a no-regret algorithm to update the reward function is not new, and using an actor-critic framework for policy updates is also common. 2. The baselines compared are not SOTA algorithms for AIL/IRL. For instance, algorithms like FILTER (Swamy, Gokul, et al., "Inverse Reinforcement Learning Without Reinforcement Learning," ICML 2023) and HyPER (Ren, Juntao, et al., "Hybrid Inverse Reinforcement Learning," arXiv preprint, 2024) outperform IQ-Learn. Minor issue: 3. For lines 270-272, the idea of using a no-regret algorithm for updating the reward function is not new. It has been explored and justified in previous work (such as Swamy, Gokul, et al., "Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap," ICML 2021).

Questions

1. Is it possible to add experiments comparing with FILTER and HyPER? I understand it is mainly a theory paper, but it would be good to add the latest SOTA algorithms to be the baselines. 2. Can FTRL directly be a justification for using off-policy update for reward function? Like, OGD is all a instance of FTRL but only update the reward function based on the current policy.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the authors have adequately addressed the limitations.