Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation
Authors: Tian Xu
Zhilong Zhang
Ruishuo Chen
Yihao Sun
Yang Yu
Venue: NeurIPS 2024 poster (2024)
Keywords: imitation learning
adversarial imitation learning
sample efficiency
Primary area: reinforcement_learning

Abstract: As a prominent category of imitation learning methods, adversarial imitation learning (AIL) has garnered significant practical success powered by neural network approximation. However, existing theoretical studies on AIL are primarily limited to simplified scenarios such as tabular and linear function approximation and involve complex algorithmic designs that hinder practical implementation, highlighting a gap between theory and practice. In this paper, we explore the theoretical underpinnings of online AIL with general function approximation. We introduce a new method called optimization-based AIL (OPT-AIL), which centers on performing online optimization for reward functions and optimism-regularized Bellman error minimization for Q-value functions. Theoretically, we prove that OPT-AIL achieves polynomial expert sample complexity and interaction complexity for learning near-expert policies. To our best knowledge, OPT-AIL is the first provably efficient AIL method with general function approximation. Practically, OPT-AIL only requires the approximate optimization of two objectives, thereby facilitating practical implementation. Empirical studies demonstrate that OPT-AIL outperforms previous state-of-the-art deep AIL methods in several challenging tasks.

Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation
Tian Xu* Zhilong Zhang 1.23, Ruishuo C, Yihao Sun and Yang Yut122
'National Key Laboratory for Novel Software Technology, Nanjing University, China School of Artificial Intelligence, Nanjing University, China
Polixinaa
Abstract
As a prominent category imitation learning methods, adversarial imitation learn- ing (AIL) has garnered significant practical success powered by neural network approximation. However, existing theoretical studies on AlL are primarily lim- ited to simplified scenarios such as tabular and linear function approximation and involve complex algorithmic designs that hinder practical implementation. highlighting gap between theory and practice. In this paper, we explore the theoretical underpinnings of online AIL with general function approximation. We introduce new method called optimization-base on performing online optimization for reward functions and optimism-reeg regularizedd Bellman error minimization for Q-value functions. Theoretically. prove that OPT-AIL achieves polynomial expert sample complexity and interaction complex- ity for learning near-expert policies. To our best knowledge, OPT-AIL is the first provably efficient AIL method with general function approximation. Practically, OPT-AIL only requires the approximate optimization of two objectives, thereby facilitating practical implementation. Empirical studies demonstrate that OPT-AIL outperforms previous state-of-the-art deep AIL methods in several challenging tasks.
AIL (OPT-AIL), which centers
Introduction
Sequential decision-making tasks are prevalent in real-world applications, where agents seek policies that maximize long-ter returns. Reinforcement learning (RL) 49 provides a well-known framework for developing effective policies through trial and error. However, RI. often necessitates carefully designed reward functions and typically requires millions of interactions with the environment to achieve satisfactory performance [36] 20) In contrast, imitation learning (II.) offers more sample- efficient approach to learning effective policies by mimicking expert demonstrations, bypassing the need for explicit reward functions. As result, IL has gained popularity and demonstrated success in wide range weal-world applications such as recommendation systems [T] 46) and generalist
robot learning 10 35|
IL encompasses two main categories of methods: behavioral cloning (BC) and adversarial imitation learning (AIL). BC employs supervised learning to directly infer expert policies from demonstration
Equal contribution. Emails: xut@lamda. .ju. edu. and zhangzl @lamda nju. edu. t: Joined this work as an undergraduate student School Mathematics, Nanjing University.
$: Corresponding author. Email: yuyenju.ert edu. edu. cn.
'The code is available at wethttpp:///e /tte://///tttbttt SAA.m/LLADAAR/OPPP..
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

data [39 44 91. In contrast, AIL utilizes an adversarial learning process to replicate the expert's s state-action distribution. This process involves the learner recovering an adversarial reward to maximize the policy value gap and subsequently learning policy that minimizes this gap under the recovered reward. Building on these foundational principles, numerous practical algorithms have been developed [55] 27
9 22
26 16 15 34 (0), achieving significant empirical advancements.
From these empirical advances, a notable observation is that AIL often significantly outperforms BC 16 26 15.. To better understand this phenomenon, recent research has focused on the theoretical underpinnings of AlL [6] 45
64 57,, particularly in the online setting. This research examines both expert sample complexity (the number of expert trajectories required) and interaction complexity (the number of trajectories needed when interacting with the environment), both of which are crucial for practical applications. In the tabular setting. the best-known complexity result is achieved in 664 They developed the MB-TAIL. algorithm, which leverages advanced distribution estimation, achieving the expert sample complexity ((11)/2|5\/s) and interaction complexity Õ(H3 ((PAA/EE)))) where |S| and [A| are the state space size and action space size, respectively, H the horizon length and e the desired value gap. Furthermore, [33 57 investigated the AIL theory in the linear function approximation setting. Notably, the BRIG approach proposed in [57] uses linear regression for policy evaluation and achieves the expert sample complexity δ (HH2/EE²) and interaction complexity Ö(H² d / where d is the feature dimension. For a complete summary of related results, please refer to [able
03
33
Despite substantial theoretical advances, there still exists a gap between theory and practice in AlL.. First, prior theoretical analysis primarily focuses on restricted settings such as tabular 41 45 64
or linear function approximation 33 577,
which deviate from practice where AlL approaches often operate with general function approximation (e.g., neural network approximation). Besides, most previous theoretical works involve algorithmic designs such as count-based [45] 64 or covariance- matrix-based [33 (57 bonuses, which are tailored to their respective settings. Implementing such algorithmic designs practical settings, where neural network approximation is employed, presents significant challenges [65] 54
Table 1: A summary of the expert sample complexity and interaction complexity. Here H is the horizon length, is the desired imitation gap. |S] is the state space size, |A| is the action space size, [T] is the cardinality of the finite policy class II, d is the dimension of the feature space, dGEc is the
generalized cluder coefficient, N (R,) and (())) are the covering numbers of the reward class R
and Q-value class Cr. respectively. We use Ô to hide logarithmic factors F
Expert Sample Complexity
Interaction Complexity
Setting
Algorithm
General Function
H2 loglmwss Mall
BC
I3
Approximation
Tabular MDPs
OAT.
45
H
A s Al
Tabular MDPs
MB-TAIL.
Ha
sP Al
Linear Mixture MDPs
OGAIL
H
Linear MDPs
BRIG
7
General Function
1f lox (maxu ((R..))
1f dase logimaxue (Ry N' ( W1RA)
OPT-AIL
Approximation
Contribution. This paper aims to bridge the gap between theory and practice in AIL by develop- ing provably efficient algorithm with general function approximation and providing practical implementation cquipped with neural networks.
First, we introduce a new AIL approach called aptimization-basee adversarial imitation learning (OPT-AIL) and provide a comprehensive theoretical analysis for general function approximation. The core of OPT-AIL involves minimizing two key objectives. To recover the reward, OPT-AIL solves an online optimization problem using a no-regret approach. For policy learning, inspired by 32 OPT-AIL infers the Q-value functions by minimizing the optimisn-regularized Bellman
We will not omit (o)()( for a function class F in θ notation since (oF()(()) could not be small for many function classes.
Herr present the result of BC in the worst case, which is consistent with this paper.

---

64 57 Early research error and then derives the corresponding greedy policies. Under mild assumptions, we prove that OPT-AIL achieves the expert sample complexity O112 log(maxne|mn) (RR)))/=² and interaction complexity O((H dorc log(maxAe Ha (W + / Here dare is the generalized eluder coefficient, originally proposed in [68] to measure the complexity of RL with function approximation, which we adapt to the AlL setting. ((RR)) and (V(2)) are the covering numbers of the reward class R2 and Q-value class 2n, respectively. To our best knowledge, OPT-AIL is the first provably efficient AIL approach with general function approximation.
Furthermore, we offer practical implementation of OPT-AIL, demonstrating its competitive per- formance on standard benchmarks. Notably, OPT-AIL only requires the approximate optimization of two objectives, simplifying its practical implementation with deep neural networks. Leverag- ing this advantage, we implement OPT-AIL using neural network approximations and compare its performance against prior offte-of-thh-art (SOTA) deep AIL methods, which often lack theoretical guarantees. Experimental results indicate that OPT-AIL outperforms SOTA deep AlL approaches on several challenging tasks within the DMControl benchmark.
2 Related Works
Adversarial Imitation Learning. The theoretical foundations of AIL have been extensively ex- plored in numerous studies [ 52
48
60)
67
41
45
33
40
63
50
56
56) focused on ideal settings where the transition function is known or an exploratory data distribution is available, primarily addressing expert sample efficiency. No- tably, under mild conditions, [63] proved that AIL can achieve horizon-free imitation gap bound (1in v [S|/N]), }), where N denotes the number of expert trajectories. Recently, new research direction has emerged that addresses more practical scenarios, specifically online AlL with unknown transitions 44 33 64 577. This line of work investigates both expert sample complexity and in- teraction complexity. These recent advancements were discussed in the previous section and thus will not be reiterated here. Most existing theoretical works focus on either tabular + 45] 64 or linear function approximation settings [33 57]. and often lack practical implementations due to algorithmic designs tailored to specific settings. In contrast, this work simultaneously provides theoretical guarantees for general function approximation and offers practical implementation that demonstrates competitive performance.
52 48 41 60,
67
62 50
On the empirical side, there has been extensive research [19
16 26 15 developing practical AIL approaches that leverage general function (or neural network) approximation. A seminal method in this field is generative adversarial imitation learning (GAIL) [19]. In GAIL, a discriminator is trained distinguish between samples from expert demonstrations and those generated by a policy, while the policy (or generator) learns to maximize the reward signal provided by the discriminator. More recently, 15] proposed inverse Q-Learning (IQLearn), which achieves SOTA performance across diverse set of tasks. However, these practical methods often lack rigorous theoretical guarantees for general function approximation.
27 28
General Function Approximation in Reinforcement Learning. Our work is closely related to a
body of research focused on general function approximation in RL (38 21 59
23
32
Notably, (32
proposed an algorithmic framework that incorporates a unified objective to balance exploration and exploitation in RL, demonstrating a sublinear regret bound. In this paper. we adapt this algorithmic design to address several RL sub-problems within the context of AIL. Unlike the RL setting, where fixed reward is provided in advance, AIL involves inferring the reward function from expert demonstrations and environment interactions collected by the learning policies. Therefore, our work requires developing a theoretical analysis for the joint learning process of both rewards and policies, highlighting a unique challenge in AIL compared to traditional RL.
3 Preliminaries
Markov Decision Process. In this paper, we consider episodic Markov Decision Processes (MDPs). represented by the tuple M (S,A, A. ,rrue H, s1). Here, S and A denote the state and action spaces, respectively. H signifies the planning horizon, while $1 stands for the fixed initial state. The set P (PI...., } characterizes the non-stationary transition function of this MDP. Specifically, (s (8n, (n)) determines the probability of transiting to state 8h+11 given state 8, and action as, at time step h, where h [H]. Similarly, pruue {r r..,, outlines the reward function of this
rtree]
MDP, Without loss of generality, we assume rh S A j0, 1] for h E [H]. A non- non-stationary
true
3

---

policy is denoted by π = { FHE with TT - (AA), where A(A) denotes the probability simplex. Here, n (als) represents the probability of selecting action a in state s time step h, for h E [H].
The quality of policy ı is evaluated by policy value:
H
V = E
true (5% ax) an ~ m)((11))) 8h+1 ~ Pal-lops on), vh E [m]
We denote the Q-value function of policy π at time step h as Q7 : S
R, where (T,(s))))
as (%, f- (st, ae) [e]ls) 18,, = 8, On. = a). The optimal Q-value function Q7 : S x A + R is defined sup= re (5, a). It is known that Q7, is the fixed point of Bellman operator Th: ()( = ( (5, a) == x (s, a) Ex s,0) |max 1 (5', In other words, Q' has zero Bellman error, i.e., Q7 0) - (Th (8, a) = =0
En D>
Imitation Learning. The essence of II. lies in acquiring high-quality policy without the reward function tru In pursuit of this objective, we typically posit the existence of a near-optimal expert policy nh capable of interacting with the environment to generate dataset, comprising N trajectories each of length H: DE = {T = (s1, a1 52, ag...., HH aH) aa ~ (- S1+1 ~ (.(-1sp.. un), Vh E [H]]. Subsequently, the learner leverages this dataset DE to mimic the behavior of the expert and thereby derives effective policy. The quality of this imitation is measured by the imitation gap 43 41]
V=* V*, where π represents the learned policy. Essentially, we hope that the learned policy can perfectly mimic the expert such that the imitation gap is small.
AIL is prominent class of IL methods that imitates expert behavior through an adversarial learning process defined by min, max, V.*" -V. where V.- denotes the value of policy π under reward r. In this framework, AIL infers a reward function that maximizes the value gap between the expert policy and the learning policy. Subsequently, it learns policy that minimizes this value gap using the inferred reward. Essentially. AlL involves solving several RL sub- uub-problems, as the outer optimization problem concerning the policy is equivalent to an RL problem under the inferred reward r.
General Function Approximation. This work considers AIL with general function approximation. In this setup, the learner first has access to reward class R R₁ R2 ... x RH with wh E [H], R, C A [0, 1]) to infer the reward. We assume that R captures the unknown true reward.
Assumption 1 (Realizability of R). The unknown true reward lies in the reward class, i.e., tre R.
Besides, the learner also has access Yh E [A] 2n C (S x A > [0, H]), which is used for solving several RL sub-problems under different inferred rewards in AlL. Since there is no reward in the H+1 step, we always set QH+1 O. Below, we present two standard assumptions about the function class Q that are commonly adopted
Q-value function class Q Q1 Q2
QH with
in the literature of RL with function approximation [59 23 68 32).
Assumption (Realizability of Q). For reward E R. Q* Q, where Q+i denotes the optimal Q-value function under reward r.
Assumption 3 (Bellman Completeness of Q). For reward r E R, Qh+1 C On, Vh E [H], where TH denotes the Bellman operator under reward r and Ty Q++1 = (T, Qn+1 Qh+1 2
In short, Assumption 2 states that the Q-value class Q should capture the optimal Q-value function, while Assumption 3 indicates the closeness of Q under Bellman update. It is easy to verify that Assumptions and are more general than the tabular MDP 45 64), linear mixture MDP 33
and linear MDP [57] assumptions used in previous works.
When the function class contains a finite number of elements, its cardinality can be used to quantify its "size". However, for general function approximation, where the function class may contain an infinite number of elements, we utilize the standard e-covering number (58) to measure its complexity.
Definition 1 (a-covering number). For function class FF C (X + R), the e-covering number of F. denoted as (F),), is defined as the minimum integer n such that there exists a finite subset F F with [F' = such that for any function E F, there exists I' FF satisfying that max,Ex (f()) - f())) S..

---

4 Optimization-based Adversarial Imitation Learning
In this section, we introduce a provably efficient method called Optimization-Base Adversarial Imitation Learning (OPT-AIL). In Section 4.1 we delve into the core components of OPT-AIL, which involves online optimization for reward functions and optimisn-reeullarieed Bellman error minimization for Q-value functions. We discuss the underlying principles and provide theoretical guarantees with general function approximation. Thanks to its easy-to-img mas-tto-implement merit, we provide a practical implementation of OPT-AIL using stochastic-grade based methods in Section 4.2
4.1 Theoretical Analysis of OPT-AIL
In this section, we present our provably efficient method OPT-AIL with general function approxima- tion; see Algorithm|] for an overview. To start with, recall that our theoretical goal is to ensure the algorithm can output a policy with e-imitation gap by using finite expert samples and environment interactions. To obtain the final policy, we leverage the standard online-to-batie conversion technique [37]. Specifically, during the learning process, the learner itcratively generates a sequence of rewards Tk=I and policies {**}
Jk= and outputs the policy मे that is uniformly sampled from {n² } Jk==' To analyze the imitation gap of тr we leverage the following standard error decomposition lemma.
{
Lemma 1. Consider a sequence of rewards {r² and policies [=") and the policy n is Tk=1" uniformly sampled from {Th) 1T=1 Then it holds that
1
V plrue
(V
V
Val
pleue
K
K
reward
policy
Lemma suggests that to achieve a small imitation gap, it is crucial to control both reward error and policy error. Specifically, reward error quantifies the distance between the true reward plrue and the learned reward r* through the imitation gap. Besides, policy error measures the value difference between the expert policy nh and the learned policy x² under the inferred reward y. Notably, this
policy error differs from the concept of regret in RL 23 32
where the reward is fixed.
To theoretically minimize the reward error and policy error, we consider an iterative approach, in which each iteration first updates the reward and subsequently derives the policy. The subsequent parts detail the reward and policy updates, which involve solving two optimization problems.
Algorithm 1 Optimization- Adversarial Imitation Learning
Input: Reward class R. Q-value class Q. initialized reward r0, policy x² and dataset D = 0. 1: for k = 2,, K do
2: Apply n k- to roll out a trajectory - and append it to the dataset DK = D U (rk-1)-
3: Obtain ,- by running a no-regret algorithm to solve the online optimization problem with
observed loss functions (r)( k-1 up to an error Epp- where ((() = nr x
4: Obtain Q* by solving the following optimization problem up to an error 2
min L (Q) BE (Q) Amax Q1 (8), QEQ
aEA
where BF* (Q) En (Q,, Qh+1; D (*) info (x Qu+1; r*).
5: Obtain n² by *5 argmax,e....... A Q% (s.
6: end for Output: म sampled uniformly from ( (KK jk=1
Reward Update via Online Optimization (Line 3 in Algorithm 1. The goal of this step is to control the reward error. More concretely, in iteration k, we aim to learn reward y* such that the error V. V - -V,55t. V,T is small. We formulate this problem as an online optimization problem. In iteration k, using the previously observed loss functions (V.** V selects n and then observes the current loss function V=*" - V. Moreover, since the previous Ji=D are not available, we instcad minimize the estimated loss
J == the reward learner
expected loss functions {V."*
V.
5

---

functions, In particular, we leverage expert demonstrations D and the trajectory r' collected by policy x' to establish an unbiased estimation (r(
V
V for V V where
H ru(sh, ab),, D.a 1
Σ TEDE
Σ
(r((((s)
N
Here (T(8N), ((an)) is the state-action pair of trajectory T visited in time step h and r' {s), ai .......................... 51 d'g) is the trajectory collected by policy n². The ultimate goal of the reward learner to minimize the cumulative losses Σk= V V= To achieve this goal, we employ no-regret algorithm [8]. In the following part, formally define the reward optimization error resulting from running the no-regret algorithm.
Definition 2 (Reward Optimization Error). For any sequence of policies {x*) Jk= the no-regret
reward optimization algorithm sequentially outputs rewards r ..... ...,. The reward optimization error ope is defined Eppt (1/K) max,eR Ek=1 V. -.
-(V=" -V.=%)
The reward optimization error, as defined above, aligns with the standard average regret in online optimization [18). a concept not extensively explored in the context of AIL. When the loss functions {C* (r) are convex functions and the reward class R. is a convex set, we can apply online projected gradient descent [18] as the no-regret algorithm, which ensures the reward optimization error Spt = O(1/ (K). As for non-convex functions and sets, employing Follow-the bollowtthe-Peruubeed Leader can similarly achieve opp = O(L/VK) 47)
Policy Update via Optimism- Regulaarze Bellman-error Minimization (Lines in Algo- rithm D. The target of policy updates is control the policy error. In iteration k; the policy learner aims to recover a policy n such that the policy error V - V,= is small, where r* is the recently recovered reward function. This is essentially an RL problem under reward function y Building upon 32. we leverage model-free approach, based Bellman error minimization, to solve this RL sub-problem. In particular, we first learn Q-value functions by solving the optimization problem of min (Q) = BE* A max (81, QEQ
atA
H (uh, Qut1; D* , Q,ERR
with BF*(Q) = Σ
inf En(O%, Qu+1; ,*),
h=1
where (Qn, Qu+1; Db. rk) (Q aih r max Qh+1 d')) D (r')
1 with T' = {s}. ai....,,yy,,. and A > 0 is the regularization coefficient. As shown in 5 233, (Q) is the estimated squared Bellman error of Q with respect to reward r. and dataset D. In this optimization problem, the main objective BE* (Q) ensures small Bellman error while the regularization term m Q1 ($1, a) tends to search an optimistic Q-value function for encouraging exploration. It is worth noting that Algorithm Tonly requires approximately solving the optimization problem up to an error op with cop L (*())) mingeg (Q). After obtaining
the Q-value function Q* we derive -² as the greedy policy of Q*.
Theoretical Guarantee of OPT-AIL. In the above part, we have explained the algorithmic mech- anisms of OPT-AIL. Now we present the theoretical guarantee. To ensure the sample efficiency of solving RL sub- sub-problems within AlL, we make structural assumption on the underlying MDP. In particular, we assume that the MDP has a small generalized eluder coefficient. This coefficient, introduced in (68), quantifies the inherent difficulty of learning the MDP with function approximation in RI.. We adapt this concept to AIL where the reward function is changing.
Assumption 4 (Low generalized eluder coefficient (68). We assume that given an e > O, the generalized eluder coefficient dGFE((E) is the smallest d (d 2 0) such that for any sequence of f K K= R,, 1Q² Jk=1 S Q and the corresponding greedy policies k Tk=1
K k-1
H
(+1, V
inf #20
E
Σ
(h((s,) (z)) -Th" Qh
an)) (0h, n²
d
24
VdHK +EHK,
where (+1, == E,y E 10t

---

Intuitively, low generalized eluder coefficient ensures that the prediction error Q4 (811 V, for x can be effectively controlled by the Bellman error the dataset generated by historical policies {x())=> Jx=1 As demonstrated in [68], the MDPs with low generalized eluder coefficient form rich class of MDPs, which covers many well-known MDP instances such tabular MDPs, linear MDPs [4 and MDPs with low Bellman eluder dimension 23 Now we are ready present the theoretical guarantee of OPT-AIL.
Theorem Under Assumptions 1 and 4 For any fixed E (0, and 8 E (0, 11, consider Algorithm with = C1 /KKH3 log [K (NN,() +
/GEC. where dGEC == de H), p== / (H=PGFF H), ei and 02 are absolute constants. Then with probability at least 8, we have that Va" V s E + & + (Copt/ /X) if the expert sample complexity and interaction complexity satisfy
H² ( N₂ (R,)18)
N
6² H' dGEc log( maxeem N (2 + +2 log
K
The proof of Theorem | can be found in Appendix B.2 Theorem indicates that when dGEC 22(1).
OPT-AIL achieves the expert sample complexity 2 (2 and interaction complexity O dGEC log( [ NNp (2n (R,))) in the general function approximation setting. To our best knowledge, OPT-AIL is the first provably efficient online AlL algorithm for general function approximation.
Notably, OPT-AIL improves over BC 13 by an order of O(H), suggesting that OPT-AIL can still provably mitigate the compounding errors issue in BC for general function approximation. When restricting Theorem [ to linear MDPs with dimension d [68), OPT-AIL can achieve the expert sample complexity O ((1=d//=)) and interaction complexity 0(11 /f//d//=)) /E"). Furthermore, when Q and R are neural network classes commonly employed practice, we can obtain the corresponding complexity result by plugging the covering number bound of neural networks (7] into Theorem [ Finally, OPT-AIL only requires the approximate optimization of two objectives, thereby facilitating practical implementation with neural networks, which will be presented in the next section.
Although Theorem ! produces desirable outcomes, it does have some limitations. One of the limitations is that Theorem | Assumption 3) Nevertheless, recent advances 4 in RL have developed new techniques remove this assumption. We leave the extension of these techniques to AlL for future work.
requires the Bellman completeness condition for the Q-value class (i.e.,
4.2 Practical Implementation of OPT-AIL
In this section, we provide practical implementation for OPT-AIL, which is based on the stochastic- gradient-based methods: see Algorithm 2 for an overview. We elaborate on the practical reward update and policy update in detail as follows.
Algorithm 2 Practical Implementation of OPT-AIL
Input: Initialized reward 0 Q-value Q", target Q-value @" = Q", policy n and dataset DO = 0. 1: for k 1, 2..... K do
2: Apply π A- to roll out a trajectory - and append it to the dataset D Dk
U f
3: Update the reward function by & <- k-1 - a, ve*(r) from Eq, 2
4: Update the Q-value function by Q² < QK- aq Ve (Q) from Eq.
5: Update the policy by = +- k-1 + (T), where (T())) = E,NDY Σ O (xn,
6: Update the target Q-value by Q. + TQ" + (1 - Q)
7: end for
Practical Reward Update. Here we detail practical implementation of the reward update by applying an online optimization approach. Recall that in 3 of Algorithm no-regret algorithm employed to solve the online optimization problem. To implement this mechanism, we choose the classical online optimization approach Follow-the Seelow-the-Reeee Leee-Rgglaiize--Laaaaa (FTRL) [2] the no-regret
7

---

approach. In iteration k, FTRL minimizes the sum of all historical loss functions with regularization.
R-
min (r) PER
Σ (r)) (((r++ + Beb(r)
i=
= k E ByNDk
Σ h=1
(s on)
E ETNDE
H Σ h=1
ra ond) + Beb(r),
where Ep[:] denotes the empirical distribution of dataset DD Here (b(r) is the regularization term. In practice, we choose (r) as the gradient penalty [6] of the reward model, which can help stabilize the learning process [27]. According to Eq. (2). the reward learner aims to maximize the value gap between the expert policy and all previous policies.
Besides, as indicated in Eq. (2). all historical samples D are utilized for the reward update. This learning style is exactly off-policy reward learning [27 [28]. In particular, applying FTRL for the reward update and offlcc reward learning share the same main objective. Previous practical works [27 28
found that this off-policy reward learning works well in practice, but could not give an explanation. In this work, we justify this off-policy learning style from an online optimization perspective: performing off-policy learning, which aligns with the FTRL approach, effectively control the reward optimization error.
Practical Policy Update. To implement the policy update in practice, adopt the actor-critic framework 04. 17 27). . In particular, we maintain policy model and Q-value model Q. Recall in line of Algorithm [ the Q-value function is learned by minimizing the pptimism-regulatizedd Bellman error. To implement this principle, following [12] 8), we leverage the temporal difference loss [3I of the Q-value model and its delayed target to upproximate the theoretical Bellman error. Then we arrive at the following objective.
H Σ
min (Q) E EYNDE QEO
Qn and - r - (1 (Q1(s1,
*- (3)
is the delayed target Q-value model. Besides, we define that Q (S x = B ( [Q++1 ($/+1, d')] where the previous greedy policy #
Here Q =
is used to approximate the maximum operator [1]. Consequently, we derive the greedy policy by optimizing the objective of max, e (IT) = Dx h= O TT).
5 Experiments
In this section, evaluate the expert sample efficiency and environment interaction efficiency of OPT-AIL through experiments. Below, we provide a brief overview of the experimental set-up, with detailed information available in Appendix due space constraints.
5.1 Experiment Set-up
We conduct experiments on 8 tasks sourced from the feature- based DMControl benchmark [53], leading benchmark in II. that offers diverse set of continuous control tasks. For each task, we adopt online DrQ-v2 [66] to train an agent with sufficient environment interactions and regard the resultant policy the expert policy. Then roll this expert policy collect expert demonstrations. Each algorithm is tested over five trials with different random seeds, and in each run, we evaluate the policy return using Monte Carlo approximation with 10 trajectories.
Environment.
Baselines. Existing theoretical AIL approaches like AB-TAIL (64] and OGAIL [33] include count- based or covariance-base based bonuses, making it challenging implement these designs when using neural network approximations. Thus, we do not include these methods in our experiments. Instead, compare OPT-AIL with prior deep IL methods, including BC [39], IQLeam [15]. PPIL [56), FILTER [5]] and HyPE 422, despite that most them lack theoretical guarantees. Notably, IQLeam, coteficalgguaaatttee
FILTER and HyPE represent prior SOTA deep AlL. approaches. To ensure fair comparison, implement all these methods within the same codehase. For detailed implementations, please refer to Appendix C

---

Cartpole Swingup
Cheetah Run
Finger Spin
Hopper Hop
150
Return
10
10
10
10
# Expert Trajectories Walker Walk
Expert Trajectories Walker Run
Expert Trajectories Walker Stand
Expert eratrces Hopper Stand
Return
430
399
380
Expert Trajectories
Expert Trajectories
Expert Trajectories
Expert Trajectories
OPT-AIL (Ours)
1QLeam
PPIL
FILTER
HyPE
BC
Expert
Figure Overall performance on 8 DMControl tasks over random seeds following 500k interactions with the environment. Here the z-axis is the number of expert trajectories and the y-axis is the return. The solid lines are the mean of results while the shaded region corresponds to the standard deviation over 5 random seeds. Same as the following figures.
Cartpole Swingup
Cheetah
Finger Spin
Hopper Hop
190
28
200k
400k
200k
400k
200k
400k
Environment Interactions Walker Walk
# Environment Interactions Walker Run
#
Environment Interactions Walker Stand
Environment Interactions Hopper Stand
Retur
28
200k
400k
200k
400k
200k
400k
200k
400k
Environment Interactions
Envirenment: Interactions
# Environment Interactions
Environment Interactions
(Ours)
IQeem
FILTER
HyPE
Expert
Figure 2: Learning curves on 8 DMControl tasks over 5 random seeds using expert trajectory. Here the x-axis is the number of environment interactions and the y-axis the return.
5.2 Experiment Results
Expert Sample Efficiency. Figure shows the performance of the learned policies after 500k environment interactions with varying numbers of expert trajectories. First, OPT-AIL significantly outperforms BC, verifying the theoretical claim that OPT-AIL can mitigate the compounding errors issue inherent in BC for general function approximation. Moreover, OPT-AIL consistently matches or exceeds the performance of prior SOTA AIL methods on all tasks. Notably, OPT-AIL demonstrates outstanding performance in scenarios with limited expert demonstrations, a common occurrence in real-world applications. In particular, when there is only one expert trajectory, our method uniquely achieves expert or near-expert performance on tasks like Finger Spin, Walker and Hopper Hop.

---

Environment Interaction Efficiency. Figure 2 displays the learning curves of different algorithms with expert trajectory. Compared with prior SOTA AlL approaches, OPT-AIL achieves comparable or better performance regarding interaction efficiency on all 8 tasks. Notably, on Hopper Hop, Walker Run and Walker Run, OPT-AIL. can achieve near-expert performance with substantially fewer environment interactions compared with prior approaches. We also demonstrate the superior interaction efficiency of OPT-AIL with other numbers of expert trajectories; please refer to Appendix for additional results.
6 Conclusions
To narrow the gap between theory and practice adversarial imitation learning, this paper investigates AlL. with general function approximation. We develop centers on performing online optimization for reward functions and optimism-regularize Bellman error minimization for Q-value functions. In theory, OPT-AIL achieves polynomial expert sample complexity and interaction complexity for general function approximation. In practice, OPT-AIL only requires approximately solving two optimization problems, which enables an efficient implementation. Our experiments demonstrate that OPT-AIL outperforms prior SOTA methods in several challenging tasks, highlighting its potential to bridge theoretical soundness with practical efficiency.
AlL approach termed OPT-AIL, which
In tabular MDPs, the currently optimal expert sample complexity is ((H)/2/e) [4 64], which is better than O /E²) attained in this paper. Therefore, a promising and valuable future direction would be to develop more advanced AIL approaches that achieve this expert sample complexity in the setting of general function approximation. Besides, [6]] established a horizon- free imitation gap bound for AlL in tabular MDPs. Thus it is interesting to explore horizon-free ffree bounds for AIL with general function approximation.
Acknowledgements
We thank Ziniu Li and Yichen Li for their helpful discussions and feedback. This work was supported by the Fundamental Research Program for Young Scholars (PhD Candidates) of the National Science Foundation of China (623B2049) and Jiangsu Science Foundation (BK20243039).
References
[1] Pieter Abbeel and Andrew Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the st International Conference Machine Learning, pages 1-8, 2004.
[2] Jacob 1) Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Proceedings of the 2 Annual Conference on Learning Theory, pages 263-274, 2008.
[3] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the 31st International Conference on Machine Learning, pages
2014.
[4] Philip Amortila, Dylan Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning. arXiv, 440109981, 2024.
[5] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71:89-129, 2008
[6] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning, pages 214-201 223, 2017.
[7] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems 30, 2017.
[8] Mohak Bhardwaj. Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng. Adversarial model for offline reinforcement learning. Advances Neural Information Processing Systems
37, 36, 2024.
10

---

[9] Kianté Brantley, Wen Sun, and Mikael Henaff. Disagreement-regulaaee imitation learning, In Proceedings of the 8th International Conference on Learning Representattonss 2020.
[10] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Xi Chen, Krzysztof Choro- manski, Tianli Ding, Danny Driess, Avinava Dubey, Chelsea Finn, al. R1-2: Vision-language- action models transfer web knowledge to robotic control. arXiv, 2307.15818. 2023.
[11] Xinshi Chen, Shuang Li, Hui Li, Shaohua Jiang, Yuan Qi, and Le Song. Generative adversarial user model for reinforcement learning based recommendation system. In Proceedings of the 36th International Conference on Machine Learming, pages 1052-1061, 2019.
[12] Ching-An An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, pages 3852-388 2022.
[13] Dylan J Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? under- standing horizon in imitation learning. arXiv, 2407. 2024.
[14] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference Machine Learning, pages 1582-1591, 2018.
[15] Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song. and Stefano Ermon. Iq-learn: Inverse soft-q learning for imitation. In Advances in Neural Information Processing Systems 34, pages 0028-4039, 2021.
[16] Seyed Kamyar Seyed Ghasemipour, Richard S. Zemel, and Shixiang Gu. A divergence minimiza- tion perspective on imitation learning methods. In Proceedings of the 3rd Annual Conference on Robot Learning, pages 1259-1277, 2019.
[17] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference on Machine Learning, pages 1856-1865, 2018
[18] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157-325, 2016.
[19] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems 29, pages 4565 4573, 2016.
[20] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems 32, pages 12498-12509 2019.
[21] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In Proceedings of the 34th International Conference on Machine Learning, pages 1704-1713,201
[22] Shengyi Jiang, Jingcheng Pang, and Yang Yu. Offline imitation learning with misspecified simulator. Advances in Neural Information Processing Systems 33, 2020.
[23] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems 34, pages 1 18406-13418 2021.
[24] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Annual Conference Learning Theory, pages 2137-2143, 2020.
[25] Yue Kang, Cho-Jui Hsich, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. Advances Neural Information Processing Systems 37, 2023.
[26] Liyiming Ke, Matt Barnes, Wen Sun, Gilwoo Lee, Sanjiban Choudhury, and Siddhartha Srinivasa. Imitation learning f-divergence minimization. arXiv, 12888, 2019.

---

[27] Ilya Kostrikov, Kumar Krishna Agrawal. Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson. Discriminator-acton citioor-atto--criiic Addressing sample inefficiency and reward bias in adversarial imitation learning. In Proceedings of the 7th International Conference on Learning Representations, 2019.
[28] Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribu- tion matching. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[29] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1179. 179- 1191, 2020.
[30] Ziniu Li, Tian Xu, Zeyu Qin, Yang Yu, and Zhi-Quar Luo. Imitation learning from imperfection: Theoretical justifications and algorithms. Advances in Neural Information Processing Systems 37, 2023.
[31] Ziniu Li, Tian Xu, and Yang Yu. A note on target q-learning for solving finite mdps with a generative oracle. arXiv, 2203. 1 1489, 2022.
[32] 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.
[33] Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Provably efficient generative adversarial imitation learning for online and offline setting with linear function approximation. arXiv, 2108.08765, 2021.
[34] Fan-Ming Luo, Xingchen Cao, Rong-Jun Qin, and Yang Yu. Transferable reward learning by gynamics-agnossee discriminator ensemble. arXiv, 2206.00238, 2022.
[35] Oier Mees, Dibya Ghosh, Karl Pertsch, Kevin Black, Homer Rich Walke, Sudeep Dasari, Joey Hejna, Tobias Kreiman, Charles Xu, Jianlan Luo, You Liang Tan, Dorsa Sadigh, Chelsea Finn, and Sergey Levine. Octo: An open-source generalist robot policy, In First Workshop Vision-Language Models for Navigation and Manipulation at ICRA 2024, 2024.
[36] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland. Georg Ostrovski, al. Humen-level control through deep reinforcement learning. Nature, 518(7540):529-53, 2015.
[37] Francesco Orabona. A modern introduction to online learning. arXiv, 1912. 2019.
[38] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems 27, pages 1466-1474, 2014.
[39] Dean Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88-97 1991.
[40] Nived Rajaraman, Yanjun Han, Lin Yang. Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation imitation learning. In Advances in Neural Information Processing Systems 34, pages 1325-1336, 2021.
[41] Nived Rajaraman, Lin F. Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamental limits of imitation learning. In Advances in Neural Information Processing Systems 33, pages 1914-2924, 2020.
[42] Juntao Ren, Gokul Swamy, Zhiwei Steven Wu, J Andrew Bagnell, and Sanjiban Choudhury. Hybrid inverse reinforcement learning. Proceedings of the 41 International Conference on Machine Learning, 2024.
[43] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In Proceedings of the 13rd International Conference on Artificial Intelligence and Statistics, pages 661-6688 2010.
12

---

[44] Stéphane Ross, Geoffrey J. Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the 14th International Conference Artificial Intelligence and Statistics, pages 627-635, 2011.
[45] Lior Shani, Tom Zahavy, and Shie Mannor. Online apprenticeship learning. arXiv, 2102.06924, 2021.
[46] Jing-Cheng Shi, Yang Yu, Qing Da, Shi- Yong Chen, and Anxiang Zeng. Virtual-taobao: virtualizing real-world online retail environment for reinforcement learning. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 4902-4909, 2019.
[47] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, pages 845-8611 2020.
[48] Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In Proceedings of the 36th International Conference Machine Learning, pages 0036-6055, 2019.
[49] Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[50] Gokul Swamy, Nived Rajaraman, Matt Peng. Sanjiban Choudhury, J Bagnell, Steven Z Wu, Jiantao Jiao, and Kannan Ramchandran. Minimax optimal online imitation learning via replay estimation. Advances in Neural Information Processing Systems 35, pages 7077-7088, 2022.
[51] Gokul Swamy, David Wu, Sanjiban Choudhury, Drew Bagnell, and Steven Wu. Inverse reinforcement learning without reinforcement learning. In Proceedings of the 40th International Conference Machine Learning, 2023.
[52] Umar Syed and Robert E. Schapire. A game-theoretic approach apprenticeship learning. In Advances in Neural Information Processing Systems 20, pages 1449-1456, 2007.
[53] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmalcki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv: 1XX1v:801.00066 2018.
[54] Daniil Tiapkin, Denis Belomestny, Éric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Piere Ménard. From dirichlet to rubin: Optimistic exploration in rl without bonuses. In Proceedings of the 39th International Conference on Machine Learning, pages 21 21380-21431, 2022.
[55] Faraz Torabi, Garrett Warnell, and Peter Stone. Behavioral cloning from observation. In Proceedings the 27th International Joint Conference on Artificial Intelligence, pages 4950- 4957, 2018
[56] Luca Viano, Angeliki Kamoutsi, Gergely Neu, Igor Krawczuk, and Volkan Cevher. Proximal point imitation learning. Advances in Neural Information Processing Systems, 35:24309-24326, 2022.
[57] Luca Viano, Stratis Skoulakis, and Volkan Cevher. Better imitation learning in discounted linear MDP, 2024.
[58] Martin J Wainwright. High-dimensional statistics: A non-asymptoric viewpoint. Cambridge University Press, 2019.
[59] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems 33, pages 6123-6135, 2020.
[60] Yizhou Wang, Tianyi Liu, Zhuoran Yang. Xingguo Li, Zhaoran Wang, and Tuo Zhao. On computation and generalization of generative adversarial imitation learning. In Proceedings of the 8th International Conference on Learning Representattions 2020.
13

---

[61] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. In Advances Neural Information Processing Systems 33, pages 15737-15749, 2020.
[62] Tian Xu, Ziniu Li, and Yang Yu. Error bounds imitating policies and environments for reinforcement learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021.
[63] Tian Xu, Ziniu Li, Yang Yu, and Zhi- thi-Quan Luo. Understanding adversarial imitation learning in small sample regime: stage-coupled analysis. arXiv, 2208.01899 2022.
[64] Tian Xu, Ziniu Li, Yang Yu, and Zhi-Quan Luo. Provably efficient adversarial imitation learning with unknown transitions. In Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, pages 2367-2378, 2023.
[65] Tianpei Yang, Hongyao Tang, Chenjia Bai. Jinyi Liu, Jianye Hao, Zhaopeng Meng, Peng Liu, and Zhen Wang. Exploration in deep reinforcement learning: comprehensive survey. arXiv, 2109.06668, 2021.
[66] Denis Yarats, Rob Fergus. Alessandro Lazaric, and Lerrel Pinto. Mastering visual continuous control: Improved data-augmented reinforcement learning. International Conference on Learning Representationss 2021.
[67] Yufeng Zhang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Generative adversarial imitation learning with neural network parameterization: Global optimality and convergence rate. In Proceedings the 37th International Conference on Machine Learning, pages 11044-11054, 2020.
[68] 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.
14

---

A Broader Impacts
This study explores the theoretical foundations adversarial imitation learning with general function approximation and demonstrates the efficiency of the proposed algorithm through standard bench- marks. Although the paper does not reveal any immediate social impacts, the potential practical applications of our research could drive positive change. By broadening the scope of adversarial imitation learning, our work may enable the creation of more efficient and effective solutions fields such roboties and autonomous vehicles. Nonetheless, consequences this technology is misused. For example, imitation learning learns from human expert demonstrations and could raise privacy concerns. Therefore, is essential ensure that the advancements in imitation learning are applied responsibly and ethically.
must recognize the potential for negative
B
Omitted Proof
B.1
Proof of Lemma
Lemma is a standard error decomposition lemma in adversarial imitation learning and variants of Lemma have appeared in [45] 57). According to the definition of オ, have that
V ptrue
V
Va pérue
ptrue
K
K
V
Vytrio
(v=
- V
+
V
V=*
K
K
ra
k=1
We complete the proof.
B.2 Proof of Theorem 1
In this section, we present the proof of Theorem
To prove Theorem T we need the following two useful lemmas which upper bound the reward error and policy error, respectively. Please refer to Appendix B.3 and B.4 for the detailed proof.
Lemma (Upper Bound on Reward Error). Under Assumption For any fixed E (0, 1], consider Algorithm 7
with probability at least - 6.
V
V
(V - V $ 2H
log 66 | N (R+))100)
+ +HHp
K
N
log(3/8)
2H
optt
Lemma 3 (Upper Bound Policy Error), Under Assumptions with probability at least - 5, holds that
2
and
For any fixed (0, 1).
57 4 log 4K max No(ONW, + 57KH Q
À
AdGEo(e')
daEc(e')H K
+ +e'H.
2K
Now we start prove Theorem
!
With Lemma ! we can derive that
K
K
E
ViTrue
1
Σ
VTB Aene
Vink
(V
1.T"
V
VT*
K
K
ph
km
Rm
15

---

Furthermore, Lemmal2 2 and Lemma ooffer upper bounds on reward error and policy error, respectively, By union bound, with probability least 1 6, we obtain
V ptroe
log (12 [ No
log(6/0)
< 2/
+ 411 + 2/1
+ opt
N
K
57H log(8K H max
(RA0
opt
X
AdGEO(E')
dGEC(E')
+
+
2K
K
We choose E' e/ HH and obtain
Vg
V
log(12 m / N₁ (R,)818)))
1og(6/0)
<
2/1
+ + 2
N
57H log (8g(8K ma
+ 57KKH
A
AdGEC
V Vuck
dGECH K
Eopt +
+
cppt
2K
where dGEC == dCEc(E/ H). By choosing the regularization coefficient
H log 8K H ] (((())),, + 114K
==
dGEC
we further obtain
V
V pizue
log(12 (R
log(6/8)
2H
4H 2H
N
K
114//-dOR log88KH maxnete
darc
& +
K
K
Copt
+ Eppt +
+E
A
log(12 ma (R((R)/8)
log(6/8)
2H
4HHHp 2H
N
K
11//4d
(8(K Ma (R.)))))
docc Hl
114H5 +
K
K
Q
Eopt A
+ Spp
+
+
log( 12 ma No (Rn)/8)
log(6/8)
< 2H V
+ 4Hp+ 2H
N
K
114H log(8K maxke N,
+ +2
54H
K
Eopt +
+ Spt
+
(6)
log(12 MaXKELH No (R,)/8))
log(6/8)
2H 2H1
+ 2H
N
K
H*dGEe (8H maxne] W,,WW,
Eopt
Q
+ +44
E +
+ 35
A
16

---

Inequality (a) follows va+b & v vb, Va 2 0 and inequality (b) holds because of the choice p p= / déFC + 4H). Now we determine the number of expert trajectories and the number of interaction trajectories. With Lemma when the expert sample complexity and interaction complexity satisfies
H log (12 ma (R.))))8)
N 2
c²
[I dGEC log log((6811)
GEC max N
(F((A)), + //2 log (6/6))
K 2304
we have that
q
V
Vrarue S 66 + Eppt +
Copt
X
Scaling e/6 completes the proof.
B.3 Proof of Lemma 2
To prove Lemma
we first perform the following error decomposition.
V yerue
Vytte
(v.z*
K
Σ
Ve ptrue
Vzz ))
+
peran
paruu
+
1
(4)
K
K
K
x
V=*"
D=
K
+
pi
and D are unbiased estimations of V.rt and V. m
Recall that for any reward function respectively.
H
H
(s ab), Vx
Σ
((((s)))7(aa)).
N
TEDR
h=1
The first term in the RHS of Eq. (4) the estimated reward error while the remaining terms estimation errors. To upper bound the first term, we have
(V
K
pizus
perao
R=
Verrn
Vytron
K
K
1
Dza - (Dat
max
K
TER
k=1
(0)
Sppt
Equation (c) follows the definition of reward optimization error in Definition 2
Then obtain
(v.** - V
Vituue
pitrue
K
K
5
B
V pk
+
V
Dz pb
+
+
pk
K
K
km
kmm
h
17

---

Then we proceed to upper bound the estimation errors. First, we first upper bound the estimation to approximate V."". In particular, have that
caused by using V
(()))()))((T))) -E TE FEDE h=1
Σ Th (sh: an)
N
H
H
Σ
- ru(sa(T);
Σ
E
r' (s an) x
N
h=1
TEDE
h=1
H
Σ
(((s)()),a(())) - E rn (1 an) a
T
N
TEDE
By Hoeffding's inequality [58]. for any fixed timestep h [H] and any fixed reward function Th Rr, with probability at least we have that
1
Σ (n)))(T)), E ma(on, an) 7
log(2/8)
N
N
TEDE
Let (Ra)p be a p-cover of R. By union bound, with probability at least Fh (Ra)p. we have that
6, for all E [H] and all
1
(n(su(F), -E Pa(sn, TEDR
Σ
{ (
mT)) am) S (2
N
N
Then with probability least 1 for all F (Fi...., (Ri), ... (R1)g-
H
Σ
(((sn(t,
E
Fn (sh an)
N
him
TEDE
H
(
N
log max (Rn))l/0)
H
N
According to the definition of p-cover, for any reward function r r= (ri,..., rH) R. there exists
F= (fi...., FB) E x.... (Ri), such that vh E [H], max(s,a)ESxA (ra(s, a) (x) S
p. Then we have that
(F) ((n)((), S Hp,
TEDE h=1
V=
E
(n(sn, an) fi an) B < Hp.
Then, with probability at least
8, for all reward function r E R, we have that
x + 2Hp
<
log(2 (2 [ (Rx)
< H
+ 211
N
(2g(2
maxkeea (Rn)/8)
< H
+ +HHp
(5)
N
Now we have obtained the upper bound on the estimation error 1i= - V Then we proceed to
upper bound the estimation error (1/K)- ===
- Va
- V and (1/K): >x
k=1 V=
V.z" With
the Hoeffding's inequality [58] 25), with probability at least - 8, we obtain that
Vitine S H log(1/6)
(6)
18

---

We proceed to analyze the term Σ V - V Notice that n are learned from historical trajecto- V ries , and thus statistically depends on , Therefore, V .... pd are not independent and the standard Hoeffding's inequality is not applicable. To address this issue, apply Azuma- Heema--nfsdding's inequality [58] for martingale. In particular, we define F as the filtration induced by {-), =²} and obtain that
1=
VI
Therefore, {(V D { inequality, derive that with probability least 1- d,
a martingale difference sequence. With Azuma-Hoeffding'
1 K
V
D
H
log(1/6)
In summary, we have derived the following three high-pree probbbbbbbbbiittyyy inequalities: Eq. Eq. 77. With union bound, with probability at least 1 - 8, it holds that
5
Eq. (6)
and
log(6 max (Rn)/0) + +2H
Vr E R, 1T - V.*
$ H
N
F plave
Vitenc
S HH
1og(3/o)
Σ
V
7 S
log(3/0
K
With the above three inequalities, we can derive that
K
(viT"
Vittonn
Vi
K
K
1 K
<
pleue
plavse
+
K
1
V
+
K
1
pleze
Vi
K
Vokk
pk
V
+
Eop
k=1
R=1
log(6 maxnemи
N (R.)/8)
log(3/8)
2H
44HHp
2H 2HH
V
We complete the proof.
B.4 Proof of Lemma
To prove Lemmal need the following two auxiliary lemmas. The detailed proof is presented in Appendix B.5 and Appendix B.6
Lemma 4. For any fixed E (0, 1}, with probubility at least
Vk E [K, (Q***) < 16H log KH max N,(QNWW,RRR)66) + 30kH p. hE[H]
Lemma 5. For any fixed 8 E (0, 1]. with probability at least 1 -. 8.
(tt(s)) (Th Qt+ (h++ ah))² 1
Vk [K], (Q*)
41H log
(2KH max
N,(eNNN,(RM)/) 27kH1 he(H]
Now we proceed to analyze the policy error. First of all, we perform the following error decomposi- tion.
V=
K
19

---

K
V
,
K Σ
(V,
(81,
(0(( 1,2²)
K
K
1=1
k=1
max Qi ($1.
max
(s), a)
+
1
Σ
(Qi()1 V,z")
K
aEA
K
Here V denotes the optimal policy value under reward n*
From line
4 in Algorithm| we know that Q* is an approximate solution of minqee (Q) with an
error Eopt. With Q from Assumption 2 we have that
(E* - À max (i(s1, a) - BE (Q Amax Qi Qi (8) 0) + Copt- aed
aEA
Rearrange the above inequality yields that
Q (81,a) max (a) S (BE*(Q -BBO)"))))B(())))) aed
opt
max aEA
From Lemma with probability at least 1 - 6, we have
< 16H log KH max N NCCCOWWS + 300HH p. RE(H]
On the other hand, with probability at least 1 Ó- ō, we have
BE (Q*)
E
(Qh(sh - -ITh ((hh m
41H log 2KH max ((WW)),,(RWW11))) 27k112 hE[H]
By union bound, with probability least 1 1-
max
Q
(),,a) max (11. aEA
aeA
H
1
Σ
E
Σ
(0i ai) -Th -i
21
1=0
57
log(4K H max N,((WN,,(RR./b3) + 57kH3 Ep...
Then have that
K
VT
V
K
kml
(h((s) af) - (Tx 15h .5).))) T²
E
2A K
5 log(4K (KK H maxNeιи (R) Ept
X
K
Σ (Qf(s) - vx²")
+ K
Now we upper bound the last term in RHS of the above inequality. From Assumption for any a 0, it holds that
K
K
(s,, x/ -V=**
ΣΣ
E
Qh(snn an) (i xt
d
K
2K
2pK
k=1
k=1i=
20

---

dH
+
K
K
k-1
H
(h() - Thi Qhmi(on,
Ad
E
+
2Xk
2K
k=
dH
+
tHH
K
The last equation is obtained by setting μ 1/2. Combining the above inequalities yields that
K
V
K
1=
57H log ma (R.)))),,(RR)))))) +
Copt
Xd
dH
+
+
+HH
A
2K
K
B.5 Proof of Lemma
Recall the definition of the estimated Bellman error.
BE*(QU
Ex Qh1T: DE, D*, inf
BE₁ (Qh, Qurli DE. ree
H k-1
@h at) - -rh ah) - max (0/ (
inf
Σ
(hh ott) -
max (
Q. E
For any fixed tuple (k, Q', E [K] H Q R, we define the random variable
()(('r)) = -s(( a'EA
max
Qi4z
-Qq Q (sh ah) ru (sh ab)
max Qfff1 (sh+1, d'EA
Furthermore, we define the filtration F% = o(((s), af...., Sn a ) U {s} ..... s H). Then we calculate the expectation and variance of Zj, (Q', r) conditioned on Fi
E (Q' ((((.r)))))) [[]]]]]]]
d'EA max Quff1 (hh)) Fi
E
Qh at)) (sh ah) +
+1 2 (s) rh (sh. ah)
(on at) - (1 ah))
max Of (1
E
Fh
d'A
(Qhish ah. Qh (sh, oht))
E
Fr
2E [chhth - (sh af) ra(sh, ah)
Q (8422) F%
max a'EA
-(h a/) (sh, ²
+ +2( ah) Q (s), (s), E (sh, at) (rh) mmx Qir (6) (6h+1, F7 ''EA
(Qh(sh) a/)) Q7 (s), (s) (sh.aa))) ?
21

---

+ +2 d/.) - 2n (s) (s), (2h" o/) (T (6h.
(5%, d//) (s) a/))²
For the conditional variance, we have that
Var
r))
Fr
< IE
(zi(Q'+))
F%
E
(0%(5) ah) Qx ah))
(2h a/) + 02 (sh. -2 (Ta(ohaah)
(2 ah) + max Qif (ifl(hhtd))) [5%]
a'EA
(
S 16H (Qh(s), a() Q (sh1
16 1/ r) Fi
Here
inequality (a) holds since (0% at) + (h, 2(ra(sh, a/)
ma Qhi1 (s) 1+1: a d'))l I 4H almost surely.
Notice that (% r) E (Z,, +)) is the martingale difference sequence adapted to K-1 Besides, almost surely, we have that
- (i'('', S max { (chlth ai) (5hh ah) - max Qh
(5 C (5)+1) (1))
d'Ed
(sh, oh)
max Q (5 (1))1,) a'EA
S <H
Then we immediately get that - s 8H2 almost surely. Thus we can apply Lemma and obtain that for any 17 E (0,1/(4HH),, with probability at least 5,
k-1
( r)
Σ E Z r)
Fi
k-1
7/'Q', (n) m||=T]
+ log (1g(
1
Σ Var
"
1=0
Σ R 1 Fb
log (1/5)
< $3672 1)
1=0
This implies that
k-1
log(1/0)
Z)(Q'r)) < (36H²1 1) Σ E Z7
,r) F)
7
< 16H log(1/6).
The last equation is obtained by choosing 1/(16H12).
We define (Qn), and (Ri)p as the p-cover of 2n and Rr. respectively. It is direct to have that 2, = (Qt), x x... (QH), and R2 = (R1), x x... x... (RH), are p-covers of Q and R, respectively. By union bound, with probability least 1 5, for all (k:, h Q, [K] x [H] 2, R,, have that
k-1 Z < 16H log KH II ((()))))))))))
H
22

---

S 16H log
KH max hE[H]
Furthermore, for any (Q,r)& Q x R, there exists (Q, 2p Rp such that 1Q - @11co S p and || al S p. Then we have that
R-1 1
k-1
k-1
Σ
22( - 2
- -
1=0
2=0
For each term, we have that
(2,))) - (Z
(oulsh ah) -ra(sh - mmx a'EA
-max 2hif1 (5) ((
d'EA h+1 (sh+1) a') 2
@nnihh a/t) - -P%( ah))
max
ox (o (sh. ah) - -6h(6h (h)
max d'EA
Qur (sh+1)
O th (sh. ob)) Fhh a/)
d'EA (irz
Q 1h
max
For the first term in RHS, we have that
ai) rs(s)h ah) - max -malhhh))
a'EA
- (Qa(sh - (fa( ah)
max Q (sh+2,
d'EA
en a/)) -rn (bh. - max Qif (8) a') + @n ob)) - -Fh(sh.
mmx 2ht1 (8
d'EA
a'Ed
@n(sh. - @n(h ahh) - -n at) + (sh a/.) max Qir (s/+1: a') + max Qh (5)+2,
d'EA
d'EA
aHl (lentos oh)) - - (5h - and + (rn(sh. - (sh.
+ max (s - Q2: d'EAA
(s (8h+2
S 12H p.
The last inequality follows Lemma 7 Similarly, for the second term in RHS, we have that
Q (5h at) - (s at.)
max a'EA
Qf (8h+1)
2
Q (sh abh) (n (5))
max Q (5/ (s)+t))
d'Ed
< 2 (sh. rn ahh
max Qi (5h+1.aa)
E'
+ 22 at)) - (sh ab)
max Q (5) a3)
ded
( af)) - Q (sh, of) - rn (sh ah) + (h ai)
2 (5h a') + max Q (s) a²))
WeA
deA
23

---

s 6H (102 (sh. -1)
2% (sh. + ( aid Fn ab)
max (sh d'EA
Qi -
S 18HH p.
Combining the above four inequalities yields that
k-1
k-1
Σ Z.0 Σ
S Σ
()( -
33kHH²
==0
1=0
Therefore, for all (Q,r) Qx
k-1 Σ Zl(0,r) S - Σ Z)( +
Σ Zx(0.r) - Zz(0A))
1=0
1=0
16/H3 log( KH max
(9N) + 30kH12p
hE[H]
16H log( KH max hE(m)
(R.)))N,(R.))00) 30khH/
This implies that
@ (K (sh, - (hh) max Qi (iif1(hh11.d))
a'EA
I inf QuERA (Qu(sh ah) -ra(sh al) max Qhi (6h42:
+ 16H (H max NC((ON),, + 30kH
hE[H]
Therefore, derive the upper bound (E
BE* (Q***)
o ON (bh) r(((hh.h)) max Thei
1=0
inf
Σ
(hishh of) ( ah) max Q (sh
E
< 16H log (KH H max N,(ON)A,(R../0)) +00hH 3
NEWH
We complete the proof.
B.6 Proof of Lemma 5
For any fixed tuple (k, Q, E [K] x [H] x Q x R, we define the random variable.
x)( = (Sh af) rx (sh a max Qu+i @ (s)=1::a))
(TT (8hh m rr (h max Qu+i (8) (sh+):)))
We define the filtration F ===o(((6 of ..... 2/1 / ) In the following part, calculate the expectation and variance of (Q, r) conditioned on Ft
E [X((Fr))
=E (Qn(sh..h) - -rn(s,, af,) max Qh+1 (s+1(s)+1. Ft
o'
24

---

(TT rn(s), ah) max (1+t1(hhth Fr
+ (Th (TTQ4+1)( (1) E
(n(s max Qn+1((h+1110)) F
(s) (is max Qn)t Fr
( F
(IT (TT(Q at) (hh ah) max Qnt1(6h+1.03) (r))
2E
((nnssh - F
2F
(Qu(th: a/) - (7)
((Thh ) max (h+z(sh++: (sh, ab) Fr
E
a
(Qn(sh af) (Th Qn 7
E
Var
S
(x)(2.)))² [F]
(Qn(th ah) + (Tx Qu+t))(hh 2ra(sho at)) max Qh+1 Q E
(Qh (/) ( QT
< 16//2B (Qu(th. of) - Q 1
= 1 (Q)
Furthermore, - (I
is a martingale difference sequence adapted to Besides, it is easy to obtain that (Q, r) I 9/12 almost surely. Thus, we can apply Lemma 6 and obtain that with probability at least 6, for any rj E (0, (/HH3))
{F))
x)(Qr)) Σ
EI
S 1 1=0
Var [x)
+ log(2/8)
1
E [X) log(2/8)
$ 16H2,
"
By choosing min(1/(9/!'),, l
[X(()))) we have that
Σ x(().)) - Σ ((
S8H
Σ [X
log(2/0) 9/1 log(2/6).
E=
This implies that
k-1
Σ ([) 8H
Σ [X
log(2/0) <
Σ x
25

---

This establishes quadratic formula of x²² br - c S 0 with x EI
b = 8H / (2/() and = Ei (2, + log (2/)) Solving this quadratic formula yields
that (b - Vb2 4c - x - (b v02 + 4c) which implies that
(b+ VB + 1c)
2 2 + b² 4c)
x² Σ
= = + 2c.
4
4
Thus we obtain that
(I S Σ (2, 82/1 ==
We define (Qh), and (Rt), as the p-covers of Qa and Rr. respectively. It is direct to have that 2₂ = (Q1), x ... (QH), and R2 = (Ri), x ... (RH), p are p-covers of Q and R, respectively. By union bound, with probability at least - 6, for all (k, h 2, [K] x [M] O, x Rp-
k-1
Σ E[X
S
x log 2K H Q 1
k-1
"
+ log
2KH II (((2))) /6)
1-0
h=1
2
F) 2 log
2KH max 1(2h)) ((Q))]]((R
hE(H]
We have calculated the conditional expectation in the LHS and obtain that
E (Qn(th. -(T)))((ThT) Q1t
1=0
1-1 (.(0..)+8211) log
2KH max hE(H]
((NN)ll(Ra)o11)
k-1
< 2 _ (2 + 12 log
2KH max N,CCN)N,(RR1186)) hE]H]
1=0
According to the definition of p-cover, for (Q#, n²),, there exists (Q. 2p R, such that
(s.0,h)ESSAx((1 ()(s. Qh(,,)) Sp
a)(ssa) - ( a)l S p.
max
max (sxa.))3SxAx(1)
Then we upper bound the errors caused by approximating (Q+, )²) with (Q,
@Qn(sh af) (T (0h(sh at) (Tr (h ob))
Qu(sh oi) -Th 1 @his oh) (Th' Qh+z) ah)
Qu(Sh, ath) - -ITh (1) Qh att) + (TH" (ht ohd
2H Qu((hh
at) - (h at) (Th" 1) ah)
6Hp.
- ,t5/|
< Qu(sh.a af.) + 2 ath) - (5h ab) - - (*th at))
26

---

mmx ( -max-maxp-
max P (S
Qn(s) 0 (h) (s ah) + a/))
max Qn+z max 2 1
(T ah) + (Th (s) ah) (/)) (1/ db))
max (n -ax max Q (8)
(nth m/) (Th'
o/) (h aht + (1)
max Qu+1 a') max (sh+1,,))
4H Qu (shh a 22 ai) (s) ab) + (s)
max (Bh max Q (sh+1,
4H
(TTQ a/) (Th 1) an)) - (Ph at) + +rh(sh,
max (5+ max (
24Hp.
With the above bounds, we can obtain that
(oh(sh ah) (Tr"" (h+1)(s,, ah))² x²)
Σ x , 8211 log 2KH max NG((O)) + 54kHHp HE(H]
1=0
According to the definition of BE we have that
(Q*)
(oh(sh, at)) - rh(sh, of)) -max Q ((thh
hm 1 O
k-1
inf Q'EQ
(h(sh (hh max Qh+z (h+z(
H 1
X ( pイ)
(h) (Tx' oh.)))
E
41H log
2KH max N,(O)W,,RR..5)) 27kH2 KE[H
Incquality (a) follows Assumption 3 that The Q
Qn We complete the proof.
27

---

B.7 Technical Lemmas
Lemma (Freedman's 's inequality B Let (Xt)STT be a real-valued martingale difference sequence
adapted to filtration Fs, and let E [-] it holds that with probability at least 1 - 8,
E[- Fel. If [Xel S almost surely, then for any nj E [0, Hl
T
log(1/6)
E n Σ
[x-1
t=1
Lemma 7. For any reward functions T, r, we have that
H
E [H), 0% (s, -5 (s,
S Σ
max [na(s,a) - -F)(8,0))
sE
M=h
Here Q* the optimal Q-value function r.
Proof. According to the Bellman optimality equation, we have that
Qh (s. a) 0% (s,a)
ra(s, a) - ()) + EgNPP((e.)
max Qu (s ,'' max
O'EA Qi-n(s',
a'EA
a)) (s, (x
a'EA ( (8', max Qi ( (s',
max Q
a'EA
We analyze the term
m (144266', (5', a²) - max 1 d')]
max 2 ( (s',
max 2 ( d'EA
a'EA
Qi a²))
a²)
Q Qiiti (5', a²) Q (s'.a));
max Qur ( (s',a') max 0 (if (s',a') d'A
d'EA
( aa)) 1 a²)
2 Q (s',a²) - @ (s a²).
(s', a'). Thus, we can get that Here al argmax Q (8', a'), a² argmax EA 2 8
Q Qi. (8', e'EA
max
max Q (f a'EA
< max a'EA
Q (8', a') Q (i
Q a') Q max d'Ed
(8)
Then we have that v(s,a) S A,
07 0 (s, u)
a' max Qi (i - max QuP
$ a (s) (xr.P(((aa)
(
d'ed
< -
max EA
Qf a')
Q 05
Applying the above recursion inequality repeatedly from h = to H' = H with (8,) Q1 (s, a) = 0 completes the proof.
Lemma 8. For a 2 1 and e < 1, when K 2 4l0g(4a/s)/s² we have that
log(aK)
s.
28

---

Proof. We consider the function f(K) Vlog(aK) K and calculate the gradient.
1 (K) 2
(log(aK) K
-1/2
(
log(aK)
K²
When K 2 /l)g(4//))/e² 4, we have that (K( S 0, implying that f(K) is monotonically
decreasing function in this range. Then we have that
log(ak) K
log (4a log (og(Aa/e)/e) Alog(4a/)
log( (B////E) + (og(log(4a/s)) + log(1/E)
4 log( (aa/e)
log( (og(4a/s) + (og(4a//)) + log (1/e)
4 4log(4a/8
S
Inequality (a) follows that log(x) S x + and inequality (b) follows that a 2 1.
C Implementation Details
C.1 Implementation Details of OPT-AIL
Reward Update. As mentioned in Section 4.2 choose (b(r in Eq. (2) the gradient penalty (GP) regularization of the reward model (6, which can help stabilize the online optimization process by enforcing I-Lipschitz continuity of the reward model Here D is linear interpolations between the replay buffer & and expert demonstrations DE
H
(()) = E
(sn, 1)?
1=11
Policy Update. Here we present the implementation details of policy updates. Firstly, to stabilize the training process, refine the optimism regularization term by subtracting baseline Q-value function from random policy = Un).(AA, which has been utilized [29 [3]. Furthermore, recognizing that initial state samples be limited and lack diversity, employ both the replay buffer D and expert demonstrations DE to compute the Q-value loss, which is a common data
augmentation approach and has been validated in many deep AlL methods [28 15 [56]. Incorporating these two enhancements, we reformulate the Q-value model training objective as follows.
H (Qn (n) an) - -u+t1s541,
min E D UDE QEO
AETNDAUDE
Σ
(Qn(sn, - Qu(shiti))
C.2 Architecture and Training Details
The experiments are conducted on a machine with 64 CPU cores and 4 RTX4090 GPU cores. Each experiment is replicated five times using different random seeds. For each task, we adopt online DrQ-v2 [66] to train an agent with sufficient environment interactions and regard the resultant policy the expert policy. Then we roll out this expert policy to collect expert demonstrations. The architecture and training details of OPT-AIL and all baselines are listed below.
33 training steps for Cheetah Run, Hopper Hop, and Walker Run, and LM training steps for other tasks.
29

---

Our codebase of OPT-AIL extends the open-sourced framework IQ We retain the structure and parameter design of the actor and critic from the original framework while employing SAC [17] with fixed temperature for policy update. We also implement a discriminator with similar architecture the critic network, and additionally incorporate layer normalization and tanh activation before the output to improve training stability. A comprehensive enumeration of the hyperparameters of OPT-AIL is provided Table 2
OPT-AIL:
BC: We implement BC based on our codebase. The actor model is trained using Mean Squared Error (MSE) loss over 10k training steps.
PPIL: We use the author's ' codebase, which is available at https//ggthuu..oo///va//////
IeLerr: We use the author's codebase, which is available at httpss//gtthuh.cmm////999999/
codebase. Due the difference in updating the discrim- inator compared to OPT-AIL,, we refer to the official DAC implementation when reproducing the discriminator. We remove the layer normalization and the tanh activation function before the output, and find that this resulted in better performance.
DAC: We reproduce the DAC based
FILTER: We use the author's codebase, which is available at https://gihuu..comm////wa/a///// irl
HyPE: We use the author's codebase, which available at https///gatuub.oommgggaaa///////
We emphasize that for a fair comparison, all algorithms are implemented using the same codehase with all hyperparameters kept consistent except for the gradient penalty coefficient. Specifically, OPT-AIL, the gradient penalty coefficient set to for Cartpole Swingup, Walker Walk, and Walker Stand, and 10 for other tasks. For baselines, the gradient penalty coefficient is always to 10 as provided by the authors. We also attempt to adjust this parameter for the baselines but find that the default parameters provided by the authors work well.
Table 2: OPT-AIL Elyper-parametert
Parameter
Value
discount (7)
0.99
gradient penalty coefficient (3)
1, 10
optimism regularization coefficient (A)
10-3
temperature (a)
10-2
replay buffer size
5- 10
batch size
256
optimizer
Adam
Diseriminator
learning rate number of hidden layers number of hidden units per layer activation
3- 10-5
2
256
ReLU
Actor
learning rate
3- 10
number of hidden layers number of hidden units per layer
2
256
activation
ReLU
Critic
learning rate
3 10-4
number of hidden layers number of hidden units per layer activation
2
256
ReLU
"The codebase of PPIL is consistent with IQLeam.
30

---

D Additional Experimental Results
In this section, we list the learning curves for 8 DMControl tasks with 4, 7, and 10 expert trajectories respectively. The corresponding results are depicted in Figure 3 Figure 4 and Figure 5 Here the x-axis is the number of environment interactions and the y-axis the return. The solid lines are the mean of results while the shaded region corresponds to the standard deviation over 5 random seeds. Our results demonstrate that OPT-AIL consistently achieves better interaction sample efficiency than state-of-the-art (SOTA) deep AIL methods, across varying numbers of expert trajectories.
Cartpole Swingup
Cheetah Run
Finger Spin
Hopper Hop
Retur
400k # Environment Interactions Walker Walk
200k
400k # Environment Interactions Walker Run
200k
200k
400k
200k
400k
# Environment Interactions Wa leee Stand
Environment Interactions Hopper Stand
330
200k Interactions
400k
200k
400k
200k
400k
200k
400k
Environment Interactions
Environment Interactions
Environment Interactions
OPT-AIL (Ours)
IQLeam
PPIL
FILTER
HyPE
BC
Expert
Figure 3: Learning curves 8 DMControl tasks over 5 random seeds using expert trajectories.
Cartpole Swingup
Cheetah
Finger Spin
Hopper Hop
159
400k
400k
EEvironment Interactions Walker Walk
Environment Interactions Walker Run
# Environment Interactions Walker Stand
Environment Interactions Hopper Stand
2.00
Retur
200k
400k
200k
400k
200k
400k
200k
400k
Environment Interactions
Environment Interactions
# Environment Interactions
Environment Interactions
(Ours)
FILTER
HyPE
Expert
Figure 4: Learning curves on 8 DMControl tasks over 5 random seeds using expert trajectories.
31

---

Cartpole Swingup
Cheetah
Finger Spin
Hopper Hop
-80
Retum
200k # Environment Interactions Walker Walk
400k
200k # Environment Interactions Walker Run
400k
200k
400k
200k Environment Interactions Happer Stand
400k
# Environment Interactions Wa Stand
1889
Return
200k
400k
200k
400k Interactions
200k
400k
200k
400k
Environment Interactions
Environment Interactions
OPT-AIL (Ours)
IQLeam
PPIL
FILTER
HyPE
BC
Expert
Figure 5: Learning curves on 8 DMControl tasks over 5 random seeds using 10 expert trajectories.
32

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly state the contribution and scope of this paper in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in Section 4.1 and Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

The full set of assumptions is stated in each theoretical result and the complete and correct proofs are provided in Appendix B
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We present all implementation details for reproducing the main experimental results of this paper in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
34

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: submit the code for reproducing the main experimental results in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccccuclccuuueeeeeeeeeeeee Coaee///ddeSSbmmmcma ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are described in Section 5 and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviation over 5 random seeds for all experiments in this paper; the detailed results in Section 5 and Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the information on the computer resources for running the experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the htt.lliie/Ehheesuideelllleee
NeurIPS Code of Ethics
Answer: [Yes]
Justification: This paper investigates the theoretical underpinnings of imitation learning and conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss both potential positive societal impacts and negative societal impacts of this work in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
36

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper conducts experiments simulated environment for continuous control and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the original paper that produced the codebase and expert dataset, and provide the corresponding URLs in Appendix
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer:[NA)
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
38

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "UDQwenNffL", "reviewer": "Reviewer_t2br", "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.", "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.\n2. 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.", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Originality: This paper introduces the first provably efficient algorithm for adversarial imitation learning (AIL) with general function approximation.\n2. Solid Mathematics: While I did not verify the proofs in the appendix, the algorithm appears standard, suggesting the proofs should be correct.\n3. 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.\n4. 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.\n2. 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.\n\nMinor issue:\n\n3. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and providing us with your valuable feedback. The references mentioned in this response can be found in the global response section.\n\n**Question 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.\n\n**Answer 1:** We would like to emphasize that the novelty of our proposed practical algorithm, OPT-AIL, lies in its unique objective function for the Q-value, as presented in Eq. (3). Unlike previous practical AIL methods such as DAC and IQLearn, which update Q-value models by minimizing the **standard** Bellman error, OPT-AIL introduces **optimism-regularized** Bellman error minimization. This optimism-based regularization encourages exploration in unknown environments, a critical feature supported by our theoretical analysis. As a result, OPT-AIL benefits from theoretical guarantees with general function approximation. In contrast, previous practical AIL methods lack this optimistic mechanism, which may lead to the absence of such theoretical guarantees in those algorithms.\n\n**Question 2:** The baselines compared are not SOTA algorithms for AIL/IRL. For instance, algorithms like FILTER and HyPER outperform IQ-Learn.\n\n**Answer 2:** Thank you for bringing these two works to our attention. To address your concerns, we conducted additional experiments on FILTER and HyPE [R1]. For [R1], due to time constraints, we focused on evaluating the model-free algorithm HyPE. We chose this approach because HyPE demonstrates a similar return to the model-based method HyPER on locomotion tasks, as reported in their paper, but with significantly shorter training time (approximately 3 hours for HyPE compared to 30 hours for HyPER per run in our experiments). We tested FILTER and HyPE using the hyperparameters recommended in their respective papers.\n\nThe detailed results are presented in Figures 1 and 2 of the submitted PDF. In terms of expert sample efficiency, OPT-AIL consistently matches or exceeds the performance of FILTER and HyPE. Regarding environment interaction efficiency, OPT-AIL achieves near-expert performance with fewer interactions compared to FILTER and HyPE. We believe this improvement could be due to the optimism-regularized Bellman error minimization technique employed in our approach, which facilitates more efficient exploration in the environment. In the revised paper, we will provide a comprehensive evaluation of FILTER, HyPE, and HyPER, and include these additional experimental results.\n\n**Question 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).\n\n**Answer 3:** We want to clarify that we do **not** claim that the application of a no-regret algorithm for reward updates is novel. Instead, in lines 270-272, we establish a **connection** between the popular off-policy reward learning and the no-regret algorithm FTRL. To the best of our knowledge, this connection is new to the imitation learning literature and offers a partial explanation for the good practical performance of off-policy reward learning. We will make this point clearer in the revised paper and include a discussion of the related work [R2].\n\n**Question 4:** 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.\n\n**Answer 4:** We establish a connection between off-policy reward learning and the Follow-The-Regularized-Leader (FTRL) algorithm by noting that **they share the same main optimization objective**. Specifically, the optimization objective for off-policy reward learning can be expressed as:\n$$\n\\min_{r \\in \\mathcal{R}} \\mathbb{E}\\_{\\tau \\sim \\mathcal{D}^k} \\left[ \\sum_{h=1}^H r_h (s^i_h, a^i_h) \\right] - \\mathbb{E}\\_{\\tau \\sim \\mathcal{D}^{\\text{E}}} \\left[ \\sum_{h=1}^H r_h (s^i_h, a^i_h) \\right]\n$$\nwhere $\\mathcal{D}^k$ represents the replay buffer containing all historical samples. For FTRL in OPT-AIL, the optimization objective can be formulated as:\n$$\n\\min_{r \\in \\mathcal{R}} \\sum_{i=0}^{k-1} \\mathcal{L}^i (r) + \\beta \\psi (r) \\Leftrightarrow \\min_{r \\in \\mathcal{R}} k \\left( \\mathbb{E}\\_{\\tau \\sim \\mathcal{D}^k} \\left[ \\sum_{h=1}^H r_h (s^i_h, a^i_h) \\right] - \\mathbb{E}\\_{\\tau \\sim \\mathcal{D}^{\\text{E}}} \\left[ \\sum_{h=1}^H r_h (s^i_h, a^i_h) \\right] \\right) + \\beta \\psi (r).\n$$\nFrom these equations, it is evident that off-policy reward learning and FTRL share the same main objective. This insight suggests that viewing off-policy reward learning through the lens of FTRL can help explain its good practical performance. However, it’s important to note that while off-policy reward learning shares this objective with FTRL, in practice, it typically involves taking several gradient steps rather than fully optimizing this objective. As such, additional analysis is required to provide a complete theoretical explanation for off-policy reward learning, which is beyond the scope of this work.\n\nFinally, we would like to clarify that OGD is an instance of FTRL only when the loss functions $\\\\{ \\mathcal{L}^i (r) \\\\}_{i=0}^K$ are linear [R3]. However, in practice, when reward models are parameterized by neural networks, the loss functions become non-linear, meaning that OGD is no longer an instance of FTRL in such cases.\n\nWe greatly appreciate your question and welcome any further inquiries.\n\n---\nWe hope that our responses can address your concerns satisfactorily. We would be grateful if you could re-evaluate our paper based on the above responses. We are \nalso willing to address any further concerns, if possible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PDf5MIjOxR", "reviewer": "Reviewer_bZiM", "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.", "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?\n2. Could the authors highlight the theoretical difficulties or novelties that arise from applying the idea of [1] to the setup of AIL?", "limitations": "Please see the weakness section and the question section above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Orginality and Significance:**\n\n1. 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.\n2. 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.\n3. Experimental results demonstrate the effectiveness of the proposed algorithm.\n\n**Quality and Clarity:**\n\nThe 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].\n2. The assumption of low generalized eluder coefficient [2] is from standard RL literature and is directly adapted here, without further explanations or discussions. \n\n**References:**\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review and provide positive feedback for our work. The references mentioned in this response can be found in the global response section.\n\n**Question 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].\n\n**Answer 1:** We want to highlight that the theoretical analysis in this paper is **not** straightforward, given existing theoretical works on AIL and RL with general function approximation (GFA). The primary technical challenge arises from the fact that, in AIL, the reward functions are dynamic and stochastic, as they are learned from expert demonstrations and environment interactions in an online manner. This introduces statistical complexity in analyzing the joint learning processes of rewards and policies. Below, we provide a more detailed explanation of these theoretical challenges and our technical solutions.\n\nUnlike in RL, the reward functions in AIL are **stochastic** and exhibit **statistical dependence**, as they are learned from sampled expert demonstrations and environment interactions. This presents technical difficulties when analyzing both reward and policy errors.\n- **Analysis of Reward Error:** Analyzing reward error involves characterizing the statistical error that arises when using an empirical loss function to approximate the expected one. However, because the reward functions are statistically dependent, standard concentration arguments for i.i.d. samples are not applicable. This challenge is **unique** to AIL with **GFA** and is not encountered in existing theoretical works on AIL [R4-R6]. Previous studies focus on either tabular [R4, R5] or linear [R6] settings, which allow for error analysis in the state-action distribution space [R4, R5] or feature expectation space [R6] in a **reward-independent** manner. In contrast, our study on the GFA setting requires error analysis in the policy value space, which is inherently **reward-dependent**. To address the statistical dependence issue, we carefully construct a martingale difference sequence and apply a martingale concentration argument.\n- **Analysis of Policy Error:** Analyzing policy error requires analyzing the difference between the empirical Bellman error, calculated from historical samples, and the true Bellman error for the recovered reward. The challenge lies in the fact that the recovered reward statistically depends on these historical samples, complicating the characterization of concentration properties. To address this, we leverage a covering number argument and design a martingale difference sequence to relate the empirical Bellman error to the true Bellman error.\n\nWe will elaborate on the theoretical challenges and our technical solutions in the revised paper.\n\n**Question 2:** The assumption of low generalized eluder coefficient [2] is from standard RL literature and is directly adapted here, without further explanations or discussions.\n\n**Answer 2:** In this work, the low generalized eluder coefficient (GEC) assumption is introduced to help control the policy error (as shown in Lemma 1) for AIL. We prove that the policy error can be upper bounded by the policy evaluation error (i.e., the term on the LHS of the low GEC assumption). The low GEC assumption ensures that the policy evaluation error can be controlled by the Bellman error on the dataset (i.e., the first term on the RHS of the low GEC assumption). By performing (regularized) Bellman error minimization, we can theoretically control the policy evaluation error, which in turn controls the policy error. We will elaborate on this low GEC assumption in the revised paper. \n\n**Question 3:** When the main theory translates to linear (or linear mixture) setups in AIL, how does the corresponding result compare with the previous arts?\n\n**Answer 3:** Here, we compare Theorem 1 with the previous result [R7] when applied to linear MDPs with dimension $d$. To adapt the main theory, we upper bound the terms $d_{\\text{GEC}}$, $\\mathcal{N}(\\mathcal{R})$, and $\\mathcal{N}(\\mathcal{Q})$ in Theorem 1 by $d$.\n\n- For $d_{\\text{GEC}}$, we can show that $d_{\\text{GEC}} = \\mathcal{O}(Hd)$. Specifically, $d_{\\text{GEC}} = \\mathcal{O}(H d_{\\text{BE}})$ [R8], where $d_{\\text{BE}}$ is the Bellman Eluder dimension. Furthermore, $d_{\\text{BE}} = \\mathcal{O}(d_{\\text{BR}})$ [R9], where $d_{\\text{BR}}$ is the Bellman rank, and $d_{\\text{BR}} \\leq d$ [R10]. Combining these bounds yields $d_{\\text{GEC}} = \\mathcal{O}(Hd)$.\n- Additionally, in linear MDPs, we use a linear reward class $\\mathcal{R}$ and a linear Q-value class $\\mathcal{Q}$. Based on the discussion following Corollary 16 in [R11], we have $\\log(\\mathcal{N}(\\mathcal{R})) = \\mathcal{O}(d)$ and $\\log(\\mathcal{N}(\\mathcal{Q})) = \\mathcal{O}(d)$.\n\nUsing these bounds, we find that in linear MDPs, OPT-AIL achieves an expert sample complexity of $\\widetilde{\\mathcal{O}}(H^2d/\\varepsilon^2)$ and an interaction complexity of $\\widetilde{\\mathcal{O}}(H^4d^2/\\varepsilon^2)$. The expert sample complexity matches that of the BRIG approach [R7], while the interaction complexity improves upon BRIG [R7] by $\\mathcal{O}(d)$. This improvement is due to the optimization-based optimism technique employed in our work, which offers better dimensional dependence than the bonus-based optimism used in [R7], as demonstrated in the RL literature [R9]. These findings confirm the sharpness of our main theory when applied to linear MDPs. We will include this discussion in the revised paper.\n\n**Question 4:** Could the authors highlight the theoretical difficulties or novelties that arise from applying the idea of [1] to the setup of AIL?\n\n**Answer 4:** We provide a detailed discussion on the theoretical challenges in **Answer 1**.  \n\n---\nWe hope that the responses given above have effectively addressed your concerns. We are open to discussing any more questions you may have, if possible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wdzu1kR9Qq", "reviewer": "Reviewer_HVwx", "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.", "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?\n- 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)?", "limitations": "I suggest the authors to include more dicussions on the primary techincal difficulties in contribution part while deriving their theoretical results for AIL.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n- This paper provides both thoeretical and empirical results to validate the proposed algorithm.\n- 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.\n- It seems that the paper mainly focus on the value-based hypothesis class and cannot incorporate the model-based ones directly.\n- The discussions on errors $\\varepsilon_{\\rm opt}^r$ and $\\varepsilon_{\\rm opt}^Q$ is not sufficient (see Questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper, and for your insightful comments. The references mentioned in this response can be found in the global response section.\n\n**Question 1:** 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.\n\n**Answer 1:** We appreciate the series of works on GEC complexity and RL with general function approximation (GFA). However, our primary focus in this work is not the study of GEC complexity. Instead, our goal is to advance the understanding of adversarial imitation learning (AIL) with GFA. To achieve this, we establish a connection between AIL and RL with GFA, based on a new theoretical error decomposition. This connection enables the development of the first provably and practically efficient AIL approach for GFA.\n\n**Question 2:** It seems that the paper mainly focus on the value-based hypothesis class and cannot incorporate the model-based ones directly.\n\n**Answer 2:** Yes, this work focuses on value-based AIL. However, designing and analyzing a model-based AIL approach by leveraging the model optimism technique proposed in [R12, R13] is a valuable direction. We expect that the online optimization-based reward update used in this work would still be compatible with model-based approaches and the policy update would need to be redesigned.\n\n**Question 3:** The discussions on errors $\\varepsilon^{r}\\_{\\text{opt}}$ and $\\varepsilon^{Q}\\_{\\text{opt}}$ is not sufficient. Can authors elaborate more on the reward update, e.g., algorithm, optimization target, a brief recap of theoretical analysis?\n\n**Answer 3:** First, we elaborate on the reward update, which is based on **online** optimization.\n\n- **Algorithm & Optimization Target:** As discussed in lines 189-197, we design the reward update based on online optimization. The goal in online optimization is to minimize regret, defined as $\\text{regret}:=\\max_{x \\in \\mathcal{X}}\\sum_{k=1}^K \\mathcal{L}^{k} (x^k) - \\mathcal{L}^{k} (x)$, with the relationship $\\varepsilon^{r}\\_{\\text{opt}} = 1/K \\cdot \\text{regret}$. To achieve this, we can apply a no-regret algorithm, which can achieve sublinear regret (e.g., $\\mathcal{O} (\\sqrt{K})$), resulting in a small $\\varepsilon_{\\text{opt}}^r$ (e.g., $\\mathcal{O} (1/\\sqrt{K})$). For instance, if we use the no-regret algorithm Follow-the-Regularized-Leader (FTRL), it updates the reward by $r^{k} \\leftarrow \\arg\\min_{r\\in\\mathcal{R}} \\sum_{i=0}^{k-1} \\mathcal{L}^{i} (r)+\\beta\\psi(r)$, where $\\psi (r)$ is the regularization function.\n\n- **Theoretical Analysis:** The key step in the analysis is **error decomposition**, which decomposes the reward error into **optimization error** and **statistical error**. We can further upper bound the optimization error by $\\varepsilon_{\\text{opt}}^r$ and analyze the statistical error using concentration theory.\n\nSecond, the Q-value update is based on **offline** optimization. In iteration $k$, we obtain $Q^{k}$ by solving the offline optimization problem $\\min_{Q \\in \\mathcal{Q}} \\mathcal{L}^k(Q)$, and the optimization error is defined as $\\varepsilon^{Q}\\_{\\text{opt}} := \\mathcal{L}^k (Q^k) - \\min_{Q \\in \\mathcal{Q}} \\mathcal{L}^k (Q)$.\n\nWe will incorporate the above discussion in the revised paper.\n\n**Question 4:** How can neural network function class be included in the architecture? What’s the complexity of such classes?\n\n**Answer 4:** This work considers a general function class including neural networks (NNs). For NNs, the expert complexity and interaction complexity of OPT-AIL depend on the covering number of NNs. Theorem 3.3 in [R14] provides the covering number bound for NNs. Consider the L-layer NNs of\n$$\n\\mathcal{F}:=\\{f_{A}:f_{A}(s, a)=\\sigma_L (A_L \\cdots \\sigma_1 (A_1 [s^T, a^T]^T))\\}.\n$$\nHere, $A_1,\\ldots,A_L$ are weight matrices with a spectral norm bound $b_s$ and a matrix norm bound $b_n$, while $\\sigma_1, \\ldots, \\sigma_L$ are activation functions with Lipschitz coefficient $\\rho$. The covering number is given by $\\log (\\mathcal{N} (\\mathcal{F})) = \\mathcal{O} ( (b_s\\rho)^{2L} ( L (b_s/b_n)^{2/3}  )^{3} )$. Substituting this bound into the original expert complexity and interaction complexity yields the results for NNs.\n\n**Question 5:** Include more dicussions on the primary techincal difficulties in contribution part while deriving their theoretical results for AIL.\n\n\n**Answer 5:** The key theoretical challenge is that, unlike in RL, the reward functions in AIL are **stochastic** and exhibit **statistical dependence**, as they are learned from sampled expert demonstrations and environment interactions. This brings technical difficulties in analyzing both reward error and policy error.\n\n- **Analysis of Reward Error:** To analyze the reward error, we need to upper bound the statistical error that arises when using the empirical loss to approximate the expected one. However, due to the statistical dependence between reward functions, the standard concentration arguments for i.i.d. samples are not applicable. To address this issue, we construct a martingale difference sequence and apply a martingale concentration argument.\n- **Analysis of Policy Error:** To analyze the policy error, we need to analyze the difference between the empirical Bellman error, calculated from historical samples, and the true Bellman error for the recovered reward. The challenge arises because the recovered reward statistically depends on the historical samples, complicating the characterization of its concentration properties. To overcome this difficulty, we use a covering number argument and then design a martingale difference sequence to relate the empirical Bellman error to the true Bellman error.\n\nWe will expand on the above discussion in the revised paper.\n\n---\nWe hope that the responses given above have effectively addressed your concerns. We are open to discussing any more questions you may have, if possible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VSYttKoiQf", "reviewer": "Reviewer_ntyv", "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.", "questions": "- why your algorithm has an expert complexity which does not depend, differently from other algorithms, on the state-action space someway?\n- 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$.\n- 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?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper analyses the AIL problem with general function approximation, which is interesting\n- Author focus on both theoretical guarantees and practical implementation\n- Authors validate the results empirically", "weaknesses": "- There are many typos. For instance:\n- line 12 \"near-expert\"\n- line 43 you say have extended, but [28] is older than [54]\n- table 1 it should be \"linear mixture\"\n- line 141 $\\mathcal{R}_h$ does not represent a reward class defined in that way\n- line 143,149 it should be \"realizability\"\n- line 145 $\\mathcal{Q}_h$ does not represent a class defined in that way\n- line 190 I think that the value functions should have an hat\n- ...\n\n- 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\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review and check our paper, and for your insightful comments. The references mentioned in this response can be found in the global response section.\n\n**Question 1:** Typos.\n\n**Answer 1:** We have fixed these typos and thoroughly revised the paper.\n\n**Question 2:** The reviewer is not sure how strong assumptions 1-4 are as structural assumptions.\n\n**Answer 2:** We point out that assumptions 1-4 in this paper are **weaker** than those used in previous theoretical AIL works [R4-R7]. Here we verify that assumptions 1-4 in this paper are weaker than the linear MDP assumption in [R7], where both the transition model and the true reward are assumed to be linear.\n\n- **Assumption 1:** [R7] assumes the true reward is linear and applies a linear reward class, which implies reward realizability.\n- **Assumption 2:** [R7] employs a linear Q-value class. Additionally, in linear MDPs, the optimal Q-value function is linear [R11], which implies Q-value realizability.\n- **Assumption 3:** Claim 7.2 in [R10] indicates that linear MDP satisfies the Bellman Completeness assumption.\n- **Assumption 4:** Linear MDP is an instance of MDPs with low GEC [R8].\n\nSimilarly, we can show that assumptions 1-4 are also weaker than the linear mixture MDP assumption in [R6]. Moreover, tabular MDP is an instance of linear MDPs and is therefore also stronger than assumptions 1-4. Overall, the assumptions used in this paper are weaker than those used in previous works [R4-R7].\n\nFurthermore, [R15] proves that the realizability and Bellman Completeness assumptions are necessary for RL with general function approximation (GFA). Since AIL requires solving a series of RL tasks, which is more complex than RL, we believe that the realizability and Bellman Completeness assumptions could be necessary for AIL with GFA. Nevertheless, it is an interesting direction to relax assumptions 1-4 in AIL with GFA.\n\n**Question 3:** Algorithm 1 requires to keep in memory all the K policies collected so far, which may be rather inefficient concerning the memory storage.\n\n**Answer 3:** Keeping historical policies is purely for sample complexity analysis and is widely applied in AIL theory works [R5, R7]. In experiments, we found that the last iterate policy already performs well, so there is no need to keep historical policies.\n\n**Question 4:** why your algorithm has an expert complexity which does not depend, differently from other algorithms, on the state-action space someway?\n\n**Answer 4:** The difference arises because our algorithm operates with **function approximation**, whereas other algorithms [R4, R5], whose expert complexities depend on the state-action space size $|\\mathcal{S}| |\\mathcal{A}|$, operates in the **tabular** setup. In AIL with **GFA**, our algorithm leverages a **reward class** $\\mathcal{R}$ to infer the true reward, and this reward class can capture the **underlying structure** of the true reward. Thus, the expert complexity depends on the complexity of $\\mathcal{R}$ (the covering number in this work) rather than on $|\\mathcal{S}| |\\mathcal{A}|$. For instance, if the true reward has a linear structure with dimension $d$ and $\\mathcal{R}$ is selected as linear functions, we have $\\log (\\mathcal{N} (\\mathcal{R})) = \\mathcal{O}(d)$, meaning the expert complexity depends on $d$. In contrast, algorithms designed for the tabular setup recover the reward value for **each state-action pair independently**, causing their expert complexities to depend on the size of the state-action space.\n\n**Question 5:** Why your algorithm can improve by an order of $H^2$ over BC? Because of the structural assumptions? Why the rate of BC is $H^4$ instead of the common $H^2$?\n\n**Answer 5:** The improvement of OPT-AIL over BC arises from the fact that OPT-AIL can acquire additional transition information from **online interactions**, whereas BC operates solely in an **offline** manner. This improvement is **not** due to the structural assumptions. By interacting with the MDP, AIL can perform multi-step state-action distribution matching [R4, R5, R7], whereas BC is limited to single-step policy matching. This insight has been theoretically validated in both tabular [R4, R5] and linear [R7] settings. In this work, we verify this insight for GFA.\n\nSecond, the $H^2$ rate for BC is achieved in the setup of **tabular MDPs** and **deterministic expert** [R16]. However, in the setting of **GFA** and **general expert** as studied in this work, Theorem 15.3 in [R10] shows that BC has an error bound $H^2 \\sqrt{\\frac{\\log (|\\Pi|)}{N}}$ when translating the result from an infinite horizon discounted MDP to a finite horizon MDP. This results in an $H^4$ expert complexity.\n\n**Question 6:** Who says that $H^{3/2} / \\varepsilon$ is the optimal rate for the GFA setting? How to break the quadratic barrier for the GFA setting?\n\n**Answer 6:** First, we want to clarify that no existing work has established that the optimal rate for GFA is $\\mathcal{O}(H^{3/2} / \\varepsilon)$. We will clarify this point in the revised paper.\n\nAdditionally, we agree with [R17] that breaking the quadratic barrier for GFA may necessitate additional assumptions about the imitation learning instance. Specifically, as discussed in [R5], to break the quadratic barrier, it might be necessary to roll out the BC policy to collect additional trajectories, enabling a more accurate estimation of the expert's state-action distribution. This approach depends on BC’s ability to achieve a low generalization error in its supervised learning (SL) task, allowing it to closely approximate the expert policy. To reach this objective, we may need to impose further assumptions on both the SL problem addressed by BC and the SL learner employed in BC.\n\n---\nWe hope that our responses can address your concerns satisfactorily. We would be grateful if you could re-evaluate our paper based on the above responses. We are also willing to address any further concerns, if possible.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Here we list all the references that appeared in the responses to reviewers.

References:

[R1] Juntao Ren et al. "Hybrid inverse reinforcement learning." arXiv: 2402.08848.

[R2] Gokul Swamy et al. "Of moments and matching: A game-theoretic framework for closing the imitation gap." ICML 2021.

[R3] Elad Hazan. "Introduction to online convex optimization." Foundations and Trends in Optimization, 2016.

[R4] Lior Shani et al. "Online apprenticeship learning." AAAI 2022.

[R5] Tian Xu et al., "Provably efficient adversarial imitation learning with unknown transitions.", UAI 2023.

[R6] Zhihan Liu et al. "Provably efficient generative adversarial imitation learning for online and offline setting with linear function approximation." ICML 2022.

[R7] Luca Viano et al. "Better imitation learning in discounted linear MDP." 2024.

[R8] Han Zhong et al. "A posterior sampling framework for interactive decision making." arXiv: 2211.01962.

[R9] Chi Jin et al. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." NeurIPS 2021.

[R10] Alekh Agarwal et al., “Reinforcement learning: Theory and algorithms.”, 2019.

[R11] Chi Jin et al. "Provably efficient reinforcement learning with linear function approximation." COLT 2020.

[R12] Simon S. Du et al. "Bilinear classes: A structural framework for provable generalization in rl." ICML 2021.

[R13] Zhihan Liu et al. "Maximize to explore: One objective function fusing estimation, planning, and exploration." NeurIPS 2023.

[R14] Peter L. Bartlett et al. "Spectrally-normalized margin bounds for neural networks." NeurIPS 2017.

[R15] Dylan J. Foster et al. "Offline reinforcement learning: Fundamental barriers for value function approximation." COLT 2022.

[R16] Nived Rajaraman et al. "Toward the fundamental limits of imitation learning." NeurIPS 2020.

[R17] Nived Rajaraman et al. "On the value of interaction and function approximation in imitation learning." NeurIPS 2021.

Meta-review: The paper proposes OPT-AIL, a novel adversarial imitation learning (AIL) algorithm with general function approximation, featuring both theoretical guarantees and empirical validation. Reviewers appreciated the solid theoretical contributions, good experimental results, and clear writing.

Reviewer t2br praised the theoretical novelty and experimental performance, suggesting minor improvements and raised the scores towards acceptance. Meanwhile, Reviewer bZiM found the paper strong and maintained a positive evaluation.

Reviewer HVwx  acknowledged the challenges addressed but noted that some techniques are standard in RL.

Reviewer ntvy pointed out some typos and assumptions but agreed with the solid contributions, but still staying slightly positive.

With reviewers in favor of the paper due to its technical soundness and practical results, I recommend acceptance of this paper as a poster presentation.
Decision: Accept (poster)