Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation

Authors: tian  xu
zhilong  zhang
ruishuo  chen
yihao  sun
yang  yu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:13:03

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.

Main paper: 
 introduction: 
 Sequential decision-making tasks are prevalent in real-world applications, where agents seek policies that maximize long-term returns. Reinforcement learning (RL) [49] provides a well-known framework for developing effective policies through trial and error. However, RL 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 (IL) offers a more sampleefficient approach to learning effective policies by mimicking expert demonstrations, bypassing the need for explicit reward functions. As a result, IL has gained popularity and demonstrated success in a wide range of real-world applications such as recommendation systems [11, 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 First, we introduce a new AIL approach called optimization-based 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 optimism-regularized Bellman error and then derives the corresponding greedy policies. Under mild assumptions, we prove that OPT-AIL achieves the expert sample complexity O(H 2 log(max h∈[H] N (R h ))/ε 2 ) and interaction complexity O((H 4 d GEC log(max h∈[H] N (Q h )N (R h )) + H 2 )/ε 2 ). Here d GEC is the generalized eluder coefficient, originally proposed in [68] to measure the complexity of RL with function approximation, which we adapt to the AIL setting. N (R h ) and N (Q h ) are the covering numbers of the reward class R h and Q-value class Q h , respectively. To our best knowledge, OPT-AIL is the first provably efficient AIL approach with general function approximation. Furthermore, we offer a practical implementation of OPT-AIL, demonstrating its competitive performance on standard benchmarks. Notably, OPT-AIL only requires the approximate optimization of two objectives, simplifying its practical implementation with deep neural networks. Leveraging this advantage, we implement OPT-AIL using neural network approximations and compare its performance against prior state-of-the-art (SOTA) deep AIL methods, which often lack theoretical guarantees. Experimental results indicate that OPT-AIL outperforms SOTA deep AIL approaches on several challenging tasks within the DMControl benchmark. 
related works: 
 Adversarial Imitation Learning. The theoretical foundations of AIL have been extensively explored in numerous studies [1, 52, 48, 60, 67, 41, 45, 33, 40, 63, 50, 56, 64, 57] . Early research [1, 52, 48, 41, 60, 67, 62, 50, 56] focused on ideal settings where the transition function is known or an exploratory data distribution is available, primarily addressing expert sample efficiency. Notably, under mild conditions, [63] proved that AIL can achieve a horizon-free imitation gap bound O(min{1, |S|/N }), where N denotes the number of expert trajectories. Recently, a new research direction has emerged that addresses more practical scenarios, specifically online AIL with unknown transitions [45, 33, 64, 57] . This line of work investigates both expert sample complexity and interaction 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 [41, 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 a practical implementation that demonstrates competitive performance.On the empirical side, there has been extensive research [19, 27, 28, 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 to 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 a diverse set of tasks. However, these practical methods often lack rigorous theoretical guarantees for general function approximation.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 a 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. 
preliminaries: 
 Markov Decision Process. In this paper, we consider episodic Markov Decision Processes (MDPs), represented by the tuple M = (S, A, P, r true , H, s 1 ). Here, S and A denote the state and action spaces, respectively. H signifies the planning horizon, while s 1 stands for the fixed initial state. The set P = {P 1 , . . . , P H } characterizes the non-stationary transition function of this MDP. Specifically, P h (s h+1 |s h , a h ) determines the probability of transiting to state s h+1 given state s h and action a h at time step h, where h ∈ [H]. Similarly, r true = {r true 1 , . . . , r true H } outlines the reward function of this MDP. Without loss of generality, we assume r true h : S × A → [0, 1] for h ∈ [H]. A non-stationary policy is denoted by π = {π 1 , . . . , π H } with π h : S → ∆(A), where ∆(A) denotes the probability simplex. Here, π h (a|s) represents the probability of selecting action a in state s at time step h, for h ∈ [H].The quality of policy π is evaluated by policy value:V π = E H h=1 r true h (s h , a h ) a h ∼ π h (•|s h ), s h+1 ∼ P h (•|s h , a h ), ∀h ∈ [H] .We denote the Q-value function of policy π at time step h as Q π h : S × A → R, whereQ π h (s, a) = E π [ H ℓ=h r true ℓ (s ℓ , a ℓ )|s h = s, a h = a]. The optimal Q-value function Q ⋆ h : S × A → R is defined as Q ⋆ h (s, a) := sup π∈Π Q π h (s, a). It is known that Q ⋆ h is the fixed point of Bellman operator T h : Q ⋆ h (s, a) = (T h Q ⋆ h+1 )(s, a) := r true h (s, a) + E s ′ ∼P h (•|s,a) [max a ′ ∈A Q ⋆ h+1 (s ′ , a ′ )]. In other words, Q ⋆ has zero Bellman error, i.e., Q ⋆ h (s, a) -(T h Q ⋆ h+1 )(s, a) = 0. Imitation Learning.The essence of IL lies in acquiring a high-quality policy without the reward function r true . In pursuit of this objective, we typically posit the existence of a near-optimal expert policy π E capable of interacting with the environment to generate a dataset, comprising N trajectories each of length H:D E = {τ = (s 1 , a 1 , s 2 , a 2 , . . . , s H , a H ) ; a h ∼ π E h (•|s h ), s h+1 ∼ P h (•|s h , a h ), ∀h ∈ [H]}.Subsequently, the learner leverages this dataset D E to mimic the behavior of the expert and thereby derives an effective policy. The quality of this imitation is measured by the imitation gap [1, 43, 41] : V π E -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 a prominent class of IL methods that imitates expert behavior through an adversarial learning process defined by min π max r V π E r -V π r , where V π r 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 a policy that minimizes this value gap using the inferred reward. Essentially, AIL involves solving several RL sub-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 a reward classR = R 1 × R 2 × . . . × R H with ∀h ∈ [H], R h ⊆ (S × 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., r true ∈ R.Besides, the learner also has access to a Q-value function classQ = Q 1 × Q 2 × . . . × Q H with ∀h ∈ [H], Q h ⊆ (S × A → [0, H]), which is used for solving several RL sub-problems under different inferred rewards in AIL. Since there is no reward in the H +1 step, we always set Q H+1 ≡ 0. Below, we present two standard assumptions about the function class Q that are commonly adopted in the literature of RL with function approximation [59, 23, 68, 32] .Assumption 2 (Realizability of Q). For reward r ∈ R, Q ⋆,r ∈ Q, where Q ⋆,r denotes the optimal Q-value function under reward r. Assumption 3 (Bellman Completeness of Q). For reward r ∈ R, T r h Q h+1 ⊆ Q h , ∀h ∈ [H],where T r h denotes the Bellman operator under reward r andT r h Q h+1 = {T r h Q h+1 : Q h+1 ∈ Q h+1 }.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 1, 2 and 3 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 ε-covering number [58] to measure its complexity.Definition 1 (ε-covering number). For function class F ⊆ (X → R), the ε-covering number of F, denoted as N ε (F), is defined as the minimum integer n such that there exists a finite subsetF ′ ⊆ F with |F ′ | = n such that for any function f ∈ F, there exists f ′ ∈ F ′ satisfying that max x∈X |f (x) -f ′ (x)| ≤ ε.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We 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. 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
optimization-based adversarial imitation learning: 
 In this section, we introduce a provably efficient method called Optimization-Based 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 optimism-regularized 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-implement merit, we provide a practical implementation of OPT-AIL using stochastic-gradient-based methods in Section 4.2.In this section, we present our provably efficient method OPT-AIL with general function approximation; see Algorithm 1 for an overview. To start with, recall that our theoretical goal is to ensure the algorithm can output a policy with ε-imitation gap by using finite expert samples and environment interactions. To obtain the final policy, we leverage the standard online-to-batch conversion technique [37] . Specifically, during the learning process, the learner iteratively generates a sequence of rewards {r k } K k=1 and policies {π k } K k=1 , and outputs the policy π that is uniformly sampled from {π k } K k=1 . To analyze the imitation gap of π, we leverage the following standard error decomposition lemma.Lemma 1. Consider a sequence of rewards {r k } K k=1 and policies {π k } K k=1 , and the policy π is uniformly sampled from {π k } K k=1 . Then it holds thatEQUATIONLemma 1 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 r true and the learned reward r k through the imitation gap. Besides, policy error measures the value difference between the expert policy π E and the learned policy π k under the inferred reward r k . 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.Input: Reward class R, Q-value class Q, initialized reward r 0 , policy π 0 and dataset D 0 = ∅.1: for k = 1, 2, . . . , K do 2:Apply π k-1 to roll out a trajectory τ k-1 and append it to the dataset D k = D k-1 ∪ {τ k-1 }.Obtain r k by running a no-regret algorithm to solve the online optimization problem with observed loss functions {L i (r)} k-1 i=0 up to an error ε r opt , whereL i (r) = V π i r -V π E r . 4:Obtain Q k by solving the following optimization problem up to an errorε Q opt . min Q∈Q L k (Q) := BE k (Q) -λ max a∈A Q 1 (s 1 , a),whereBE k (Q) = H h=1 E h (Q h , Q h+1 ; D k , r k ) -inf Q ′ h ∈Q h E h (Q ′ h , Q h+1 ; D k , r k ). 5: Obtain π k by π k h (s) = argmax a∈A Q k h (s, a). 6: end for Output: π sampled uniformly from {π k } K k=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 a reward r k such that the errorV π k r k -V π E r k -(V π k r true -V π E r true) is small. We formulate this problem as an online optimization problem. In iteration k, using the previously observed loss functions{V π i r -V π E r } k-1 i=0, the reward learner selects r k and then observes the current loss functionV π k r -V π Er . Moreover, since the previous expected loss functions{V π i r -V π E r } k-1 i=0are not available, we instead minimize the estimated loss functions. In particular, we leverage expert demonstrations D E and the trajectory τ i collected by policy π i to establish an unbiased estimationL i (r) = V π i r -V π E r for V π i r -V π E r, whereV π i r = H h=1 r h (s i h , a i h ), V π E r = 1 N τ ∈D E H h=1 r h (τ (s h ), τ (a h )).Here (τ (s h ), τ (a h )) is the state-action pair of trajectory τ visited in time step h and τ i = {s i 1 , a i 1 , . . . , s i H , a i H } is the trajectory collected by policy π i . The ultimate goal of the reward learner is to minimize the cumulative lossesK k=1 V π k r k -V π E r k .To achieve this goal, we employ a no-regret algorithm [18] . In the following part, we formally define the reward optimization error resulting from running the no-regret algorithm. Definition 2 (Reward Optimization Error). For any sequence of policies {π k } K k=1 , the no-regret reward optimization algorithm sequentially outputs rewards r 1 , . . . , r K . The reward optimization error ε r opt is defined asε r opt := (1/K) • max r∈R K k=1 V π k r k -V π E r k -( V π k r -V π E r). 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 {L k (r)} K k=0 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 ε r opt = O(1/ √ K). As for non-convex functions and sets, employing Follow-the-Perturbed-Leader can similarly achieve ε r opt = O(1/ √ K) [47] .Policy Update via Optimism-Regularized Bellman-error Minimization (Lines 4-5 in Algorithm 1). The target of policy updates is to control the policy error. In iteration k, the policy learner aims to recover a policy π k such that the policy errorV π E r k -V π k r k is small, where r k is the recently recovered reward function. This is essentially an RL problem under reward function r k . Building upon [32] , we leverage a model-free approach, based on Bellman error minimization, to solve this RL sub-problem. In particular, we first learn Q-value functions by solving the optimization problem ofmin Q∈Q L k (Q) := BE k (Q) -λ max a∈A Q 1 (s 1 , a), with BE k (Q) = H h=1 E h (Q h , Q h+1 ; D k , r k ) -inf Q ′ h ∈Q h E h (Q ′ h , Q h+1 ; D k , r k ),whereE h (Q h , Q h+1 ; D k , r k ) = k-1 i=0 (Q h (s i h , a i h ) -r k h -max a ′ ∈A Q h+1 (s i h+1 , a ′ )) 2 , D k = {τ i } k-1i=0 with τ i = {s i 1 , a i 1 , . . . , s i H , a i H } and λ > 0 is the regularization coefficient. As shown in [5, 23] , BE k (Q) is the estimated squared Bellman error of Q with respect to reward r k and dataset D k . In this optimization problem, the main objective BE k (Q) ensures a small Bellman error while the regularization term max a∈A Q 1 (s 1 , a) tends to search an optimistic Q-value function for encouraging exploration. It is worth noting that Algorithm 1 only requires approximately solving the optimization problem up to an error εQ opt with ε Q opt = L k (Q k ) -min Q∈Q L k (Q).After obtaining the Q-value function Q k , we derive π k as the greedy policy of Q k .Theoretical Guarantee of OPT-AIL. In the above part, we have explained the algorithmic mechanisms of OPT-AIL. Now we present the theoretical guarantee. To ensure the sample efficiency of solving RL sub-problems within AIL, we make a 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 RL. We adapt this concept to AIL where the reward function is changing. Assumption 4 (Low generalized eluder coefficient [68] ). We assume that given an ε > 0, the generalized eluder coefficient d GEC (ε) is the smallest d (d ≥ 0) such that for any sequence of{r k } K k=1 ⊆ R, {Q k } K k=1 ⊆ Q and the corresponding greedy policies {π k } K k=1 , K k=1 Q k 1 (s 1 , π k ) -V π k r k ≤ inf µ≥0 µ 2 K k=1 k-1 i=1 E H h=1 Q k h (s h , a h ) -T r k h Q k h+1 (s h , a h ) 2 π i + d 2µ + √ dHK + εHK, where Q k 1 (s 1 , π k ) := E a1∼π k 1 (•|s1) [Q k 1 (s 1 , a 1 )].Intuitively, a low generalized eluder coefficient ensures that the prediction error Q k 1 (s 1 , π k ) -V π k r k for π k can be effectively controlled by the Bellman error on the dataset generated by historical policies {π i } k-1 i=1 . As demonstrated in [68] , the MDPs with low generalized eluder coefficient form a rich class of MDPs, which covers many well-known MDP instances such tabular MDPs, linear MDPs [24] and MDPs with low Bellman eluder dimension [23] . Now we are ready to present the theoretical guarantee of OPT-AIL. Theorem 1. Under Assumptions 1, 2, 3 and 4. For any fixed ε ∈ (0, 1] and δ ∈ (0, 1], consider Algorithm 1 with λ = c 1 (KH 3 log(4KHN ρ (Q)N ρ (R)/δ) + K 2 H 3 ρ)/d GEC , where d GEC := d GEC (ε/H), ρ := c 2 ε 2 /(H 2 d GEC + H), c 1 and c 2 are absolute constants. Then with probability at least 1 -δ, we have thatV π E -V π ≤ ε + ε r opt + (ε Q opt /λ) if the expert sample complexity and interaction complexity satisfyN ≳ H 2 log(max h∈[H] N ρ (R h )/δ) ε 2 , K ≳ H 4 d GEC log(Hd GEC max h∈[H] N ρ (Q h )N ρ (R h )/(δε)) + H 2 log(1/δ) ε 2 .The proof of Theorem 1 can be found in Appendix B. Finally, OPT-AIL only requires the approximate optimization of two objectives, thereby facilitating a practical implementation with neural networks, which will be presented in the next section.Although Theorem 1 produces desirable outcomes, it does have some limitations. One of the limitations is that Theorem 1 requires the Bellman completeness condition for the Q-value class (i.e., Assumption 3). Nevertheless, recent advances [4] in RL have developed new techniques to remove this assumption. We leave the extension of these techniques to AIL for future work.In this section, we provide a practical implementation for OPT-AIL, which is based on the stochasticgradient-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-AILInput: Initialized reward r 0 , Q-value Q 0 , target Q-value Q 0 = Q 0 , policy π 0 and dataset D 0 = ∅. 1: for k = 1, 2, . . . , K do 2:Apply π k-1 to roll out a trajectory τ k-1 and append it to the datasetD k = D k-1 ∪ {τ k-1 }. 3:Update the reward function by r k ← r k-1 -α r ∇ℓ k (r) from Eq. ( 2).Update the Q-value function byQ k ← Q k-1 -α Q ∇ℓ k (Q) from Eq. (3). 5:Update the policy byπ k ← π k-1 + α π ∇ℓ k (π), where ℓ k (π) := E τ ∼D k [ H h=1 Q k h (s h , π)]. 6: Update the target Q-value by Q k ← τ Q k + (1 -τ )Q k-17: end for Practical Reward Update. Here we detail a practical implementation of the reward update by applying an online optimization approach. Recall that in line 3 of Algorithm 1, a no-regret algorithm is employed to solve the online optimization problem. To implement this mechanism, we choose the classical online optimization approach Follow-the-Regularized-Leader (FTRL) [2] as the no-regret approach. In iteration k, FTRL minimizes the sum of all historical loss functions with a regularization.EQUATIONwhere E D [•] denotes the empirical distribution of dataset D. Here ψ(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 k 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 off-policy 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, can effectively control the reward optimization error.Practical Policy Update. To implement the policy update in practice, we adopt the actor-critic framework [14, 17, 27] . In particular, we maintain a policy model π and a Q-value model Q. Recall in line 4 of Algorithm 1, the Q-value function is learned by minimizing the optimism-regularized Bellman error. To implement this principle, following [12, 8] , we leverage the temporal difference loss [31] of the Q-value model and its delayed target to approximate the theoretical Bellman error.Then we arrive at the following objective.EQUATIONHereQ = {Q 1 , . . . , Q H } is the delayed target Q-value model. Besides, we define that Q k-1 h+1 (s h+1 , π k-1 ) := E a ′ ∼π k-1 h+1 (•|s h+1 ) [Q h+1 (s h+1 , a ′ )]where the previous greedy policy π k-1 is used to approximate the maximum operator [17] . Consequently, we derive the greedy policy by optimizing the objective of max π ℓ k (π) := E τ ∼D k [ H h=1 Q k h (s h , π)]. 
experiments: 
 In this section, we 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 C due to space constraints.Environment. We conduct experiments on 8 tasks sourced from the feature-based DMControl benchmark [53] , a leading benchmark in IL that offers a 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 as the expert policy. Then we roll out this expert policy to 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.Baselines. Existing theoretical AIL approaches like MB-TAIL [64] and OGAIL [33] include countbased or covariance-based bonuses, making it challenging to implement these designs when using neural network approximations. Thus, we do not include these methods in our experiments. Instead, we compare OPT-AIL with prior deep IL methods, including BC [39] , IQLearn [15] , PPIL [56] , FILTER [51] and HyPE [42] , despite that most of them lack theoretical guarantees. Notably, IQLearn, FILTER and HyPE represent prior SOTA deep AIL approaches. To ensure a fair comparison, we implement all these methods within the same codebase. For detailed implementations, please refer to Appendix C. Here the x-axis is the number of environment interactions and the y-axis is the return.Expert Sample Efficiency. Figure 1 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 Run and Hopper Hop.Environment Interaction Efficiency. Figure 2 displays the learning curves of different algorithms with 1 expert trajectory. Compared with prior SOTA AIL 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 D for additional results. 
conclusions: 
 To narrow the gap between theory and practice in adversarial imitation learning, this paper investigates AIL with general function approximation. We develop a new AIL approach termed OPT-AIL, which centers on performing online optimization for reward functions and optimism-regularized 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.In tabular MDPs, the currently optimal expert sample complexity is O(H  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper conducts experiments on a 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 a 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 to 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 we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.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 C.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?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. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: This study explores the theoretical foundations of adversarial imitation learning with general function approximation and demonstrates the efficiency of the proposed algorithm through standard benchmarks. 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 in fields such as robotics and autonomous vehicles. Nonetheless, we must recognize the potential for negative consequences if this technology is misused. For example, imitation learning learns from human expert demonstrations and could raise privacy concerns. Therefore, it is essential to ensure that the advancements in imitation learning are applied responsibly and ethically.Lemma 1 is a standard error decomposition lemma in adversarial imitation learning and variants of Lemma 1 have appeared in [45, 57] . According to the definition of π, we have thatV π E -V π = V π E r true -V π r true = 1 K K k=1 V π E r true -V π k r true = 1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k + 1 K K k=1 V π E r k -V π k r k .We complete the proof.In this section, we present the proof of Theorem 1.To prove Theorem 1, 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 2 (Upper Bound on Reward Error). Under Assumption 1. For any fixed δ ∈ (0, 1], consider Algorithm 1, with probability at least 1 -δ,1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k ≤ 2H log(6 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(3/δ) K + ε r opt .Lemma 3 (Upper Bound on Policy Error). Under Assumptions 2, 3 and 4. For any fixed δ ∈ (0, 1], with probability at least 1 -δ, it holds that1 K K k=1 V π E r k -V π k r k ≤ 57H 4 log(4KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57KH 3 ρ + ε Q opt λ + λd GEC (ε ′ ) 2K + d GEC (ε ′ )H K + ε ′ H.Now we start to prove Theorem 1. With Lemma 1, we can derive thatV π E r true -V π r true = 1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k + 1 K K k=1 V π E r k -V π k r k .Furthermore, Lemma 2 and Lemma 3 offer upper bounds on reward error and policy error, respectively. By union bound, with probability at least 1 -δ, we obtainV π E r true -V π r true ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(6/δ) K + ε r opt + 57H 4 log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57KH 3 ρ + ε Q opt λ + λd GEC (ε ′ ) 2K + d GEC (ε ′ )H K + ε ′ H.We choose ε ′ = ε/H and obtainV π E r true -V π r true ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(6/δ) K + 57H 4 log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57KH 3 ρ λ + λd GEC 2K + d GEC H K + ε r opt + ε Q opt λ + ε,whered GEC := d GEC (ε/H). By choosing the regularization coefficient λ = 114KH 4 log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 114K 2 H 3 ρ d GEC ,we further obtainV π E r true -V π r true ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(6/δ) K + 114H 4 d GEC log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) K + 114H 3 d GEC ρ + d GEC H K + ε r opt + ε Q opt λ + ε (a) ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(6/δ) K + 114H 4 d GEC log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) K + 114H 3 d GEC ρ + d GEC H K + ε r opt + ε Q opt λ + ε ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(6/δ) K + 2 114H 4 d GEC log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) K + 54H 3 d GEC ρ + ε r opt + ε Q opt λ + ε (b) ≤ 2H log(12 max h∈[H] N ρ (R h )/δ) N + 2H log(6/δ) K + 24 H 4 d GEC log(8KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) K + ε r opt + ε Q opt λ + 3εInequality (a) follows√ a + b ≤ √ a + √ b,∀a, b ≥ 0 and inequality (b) holds because of the choice ρ = ε 2 /(54H 3 d GEC + 4H). Now we determine the number of expert trajectories and the number of interaction trajectories. With Lemma 8, when the expert sample complexity and interaction complexity satisfiesN ≥ 4 H 2 log(12 max h∈[H] N ρ (R h )/δ) ε 2 , K ≥ 2304 (H 4 d GEC log(768H 5/2 d 1/2 GEC max h∈[H] N ρ (Q h )N ρ (R h )/(δε)) + H 2 log(6/δ)) ε 2 ,we have thatV π E r true -V π r true ≤ 6ε + ε r opt + ε Q opt λ .Scaling ε as ε/6 completes the proof.To prove Lemma 2, we first perform the following error decomposition.EQUATIONRecall that for any reward function r, V π i r and V π E r are unbiased estimations of V π i r and V π E r , respectively.V π i r = H h=1 r h (s i h , a i h ), V π E r = 1 N τ ∈D E H h=1 r h (τ (s h ), τ (a h )).The first term in the RHS of Eq. ( 4) is the estimated reward error while the remaining terms are estimation errors. To upper bound the first term, we have1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k = 1 K K k=1 V π k r k -V π E r k -V π k r true -V π E r true ≤ 1 K max r∈R K k=1 V π E r k -V π k r k -V π k r -V π E r (c)= ε r opt . Equation (c) follows the definition of reward optimization error in Definition 2. Then we can obtain1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k ≤ V π E r true -V π E r true + 1 K K k=1 V π E r k -V π E r k + 1 K K k=1 V π k r true -V π k r true + 1 K K k=1 V π k r k -V π k r k + ε r opt .Then we proceed to upper bound the estimation errors. First, we first upper bound the estimation error caused by using V π E r to approximate V π E r . In particular, we have thatV π E r -V π E r = 1 N τ ∈D E H h=1 r h (s h (τ ), a h (τ )) -E H h=1 r h (s h , a h ) π E = H h=1 1 N τ ∈D E r h (s h (τ ), a h (τ )) - H h=1 E r h (s h , a h ) π E ≤ H h=1 1 N τ ∈D E r h (s h (τ ), a h (τ )) -E r h (s h , a h ) π E .By Hoeffding's inequality [58] , for any fixed timestep h ∈ [H] and any fixed reward function r h ∈ R h , with probability at least 1 -δ, we have that1 N τ ∈D E r h (s h (τ ), a h (τ )) -E r h (s h , a h ) π E ≤ log(2/δ) N .Let (R h ) ρ be a ρ-cover of R. By union bound, with probability at least 1 -δ, for all h ∈ [H] and all r h ∈ (R h ) ρ , we have that1 N τ ∈D E r h (s h (τ ), a h (τ )) -E r h (s h , a h ) π E ≤ log(2H|(R h ) ρ |/δ) N .Then with probability at least 1 -δ, for all r = ( r 1 , . . . , rH ) ∈ (R 1 ) ρ × . . . × (R 1 ) ρ , V π E r -V π E r ≤ H h=1 1 N τ ∈D E r h (s h (τ ), a h (τ )) -E r h (s h , a h ) π E ≤ H h=1 log(2|(R h ) ρ |/δ) N ≤ H log(2 max h∈[H] |(R h ) ρ |/δ) N .According to the definition of ρ-cover, for any reward function r = (r 1 , . . . , r H ) ∈ R, there exists r = ( r 1 , . . . , r H ) ∈ (R 1 ) ρ ×. . .×(R 1 ) ρ such that ∀h ∈ [H], max (s,a)∈S×A |r h (s, a)-r h (s, a)| ≤ ρ. Then we have thatV π E r -V π E r ≤ 1 N τ ∈D E H h=1 |r h (s h (τ ), a h (τ )) -r h (s h (τ ), a h (τ ))| ≤ Hρ, V π E r -V π E r ≤ E H h=1 |r h (s h , a h ) -r h (s h , a h )| π E ≤ Hρ.Then, with probability at least 1 -δ, for all reward function r ∈ R, we have thatEQUATIONNow we have obtained the upper bound on the estimation error| V π E r -V π E r |.Then we proceed to upper bound the estimation error(1/K) • K k=1 V π k r true -V π k r true and (1/K) • K k=1 V π k r k -V π k r k .With the Hoeffding's inequality [58, 25] , with probability at least 1 -δ, we obtain thatEQUATIONWe proceed to analyze the termK k=1 V π k r k -V π k r k .Notice that r k are learned from historical trajectories {τ 1 , . . . , τ k-1 } and thus statistically depends on {τ 1 , . . . , τ k-1 }. Therefore, V π 1 r 1 , • • • , V π k r k are not independent and the standard Hoeffding's inequality is not applicable. To address this issue, we apply Azuma-Hoeffding's inequality [58] for martingale. In particular, we define F k as the filtration induced by {τ 1 , • • • , τ k } and can obtain thatE V π k r k -V π k r k |F k-1 = 0. Therefore, {(V π k r k -V π k r k , F k )} ∞k=1 is a martingale difference sequence. With Azuma-Hoeffding's inequality, we can derive that with probability at least 1 -δ,EQUATIONIn summary, we have derived the following three high-probability inequalities: Eq. ( 5), Eq. ( 6) and Eq. (7) . With union bound, with probability at least 1 -δ, it holds that∀r ∈ R, V π E r -V π E r ≤ H log(6 max h∈[H] N ρ (R h )/δ) N + 2Hρ, 1 K K k=1 V π k r true -V π k r true ≤ H log(3/δ) K , 1 K K k=1 V π k r k -V π k r k ≤ H log(3/δ) K .With the above three inequalities, we can derive that1 K K k=1 V π E r true -V π k r true -V π E r k -V π k r k ≤ V π E r true -V π E r true + 1 K K k=1 V π E r k -V π E r k + 1 K K k=1 V π k r true -V π k r true + 1 K K k=1 V π k r k -V π k r k + ε r opt ≤ 2H log(6 max h∈[H] N ρ (R h )/δ) N + 4Hρ + 2H log(3/δ) K + ε r opt .We complete the proof.To prove Lemma 3, we need the following two auxiliary lemmas. The detailed proof is presented in Appendix B.5 and Appendix B.6. Lemma 4. For any fixed δ ∈ (0, 1], with probability at least 1 -δ,∀k ∈ [K], BE k (Q ⋆,r k ) ≤ 16H 4 log KH max h∈[H] N ρ (Q h )N ρ (R h )/δ + 30kH 3 ρ.Lemma 5. For any fixed δ ∈ (0, 1], with probability at least 1 -δ,∀k ∈ [K], BE k (Q k ) ≥ 1 2 k-1 i=0 E H h=1 Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i -41H 4 log 2KH max h∈[H] N ρ (Q h )N ρ (R h )/δ -27kH 2 ρ.Now we proceed to analyze the policy error. First of all, we perform the following error decomposition.1 K K k=1 V π E r k -V π k r k ≤ 1 K K k=1 V ⋆ r k -V π k r k = 1 K K k=1 V ⋆ r k -Q k 1 (s 1 , π k ) + 1 K K k=1 Q k 1 (s 1 , π k ) -V π k r k = 1 K K k=1 max a∈A Q ⋆,r k 1 (s 1 , a) -max a∈A Q k 1 (s 1 , a) + 1 K K k=1 Q k 1 (s 1 , π k ) -V π k r k .Here V ⋆ r k denotes the optimal policy value under reward r k . From line 4 in Algorithm 1, we know thatQ k is an approximate solution of min Q∈Q L k (Q) with an error ε Q opt . With Q ⋆,r k ∈ Q from Assumption 2, we have that BE k (Q k ) -λ max a∈A Q k 1 (s 1 , a) ≤ BE k (Q ⋆,r k ) -λ max a∈A Q ⋆,r k 1 (s 1 , a) + ε Q opt .Rearrange the above inequality yields thatmax a∈A Q ⋆,r k 1 (s 1 , a) -max a∈A Q k 1 (s 1 , a) ≤ 1 λ BE k (Q ⋆,r k ) -BE k (Q k ) + ε Q opt λ .From Lemma 4, with probability at least 1 -δ, we haveBE k (Q ⋆,r k ) ≤ 16H 4 log KH max h∈[H] N ρ (Q h )N ρ (R h )/δ + 30kH 3 ρ.On the other hand, with probability at least 1 -δ, we haveBE k (Q k ) ≥ 1 2 k-1 i=0 E H h=1 Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i -41H 4 log 2KH max h∈[H] N ρ (Q h )N ρ (R h )/δ -27kH 2 ρ.By union bound, with probability at least 1 -δ,max a∈A Q ⋆,r k 1 (s 1 , a) -max a∈A Q k 1 (s 1 , a) ≤ - 1 2λ k-1 i=0 E H h=1 Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i + 57H 4 log(4KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57kH 3 ρ + ε Q opt λ .Then we have that1 K K k=1 V π E r k -V π k r k ≤ - 1 2λ 1 K K k=1 k-1 i=0 E H h=1 Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i + 57H 4 log(4KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57KH 3 ρ + ε Q opt λ + 1 K K k=1 Q k 1 (s 1 , π k ) -V π k r k. Now we upper bound the last term in RHS of the above inequality. From Assumption 4, for any µ ≥ 0, it holds that1 K K k=1 Q k 1 (s 1 , π k ) -V π k r k ≤ µ 2K K k=1 k-1 i=1 E H h=1 Q k h (s h , a h ) -T r k h Q k h+1 (s h , a h ) 2 π i + d 2µK + dH K + εH = 1 2λK K k=1 k-1 i=1 E H h=1 Q k h (s h , a h ) -T r k h Q k h+1 (s h , a h ) 2 π i + λd 2K + dH K + εH.The last equation is obtained by setting µ = 1/λ. Combining the above two inequalities yields that1 K K k=1 V π E r k -V π k r k ≤ 57H 4 log(4KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 57KH 3 ρ + ε Q opt λ + λd 2K + dH K + εH.Recall the definition of the estimated Bellman error.BE k (Q ⋆,r k ) = H h=1 E h (Q ⋆,r k h , Q ⋆,r k h+1 ; D k , r k ) -inf Q ′ h ∈Q h BE h (Q ′ h , Q ⋆,r k h+1 ; D k , r k ) = H h=1 k-1 i=0 Q ⋆,r k h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q ⋆,r k h+1 (s i h+1 , a ′ ) 2 -inf Q ′ h ∈Q h k-1 i=0 Q ′ h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q ⋆,r k h+1 (s i h+1 , a ′ ) 2 .For any fixed tuple(k, h, Q ′ , r) ∈ [K] × [H] × Q × R, we define the random variable Z i h (Q ′ , r) := Q ′ h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 -Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 .Furthermore, we define the filtrationF i h = σ({(s j 1 , a j 1 , . . . , s j H , a j H )} i-1 j=0 ∪ {s i 1 , a i 1 , . . . , s i h , a i h }).i h (Q ′ , r) conditioned on F i h . E Z i h (Q ′ , r)|F i h = E Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) + Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 F i h -E Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 F i h = E Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) 2 F i h + 2E Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) F i h = Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) 2 + 2 Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) E Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) F i h = Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) + 2 Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) Q ⋆,r h (s i h , a i h ) -(T r h Q ⋆,r h+1 )(s i h , a i h ) = Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) 2 .For the conditional variance, we have thatVar Z i h (Q ′ , r) F i h ≤ E Z i h (Q ′ , r) 2 F i h = E Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) 2 • Q ′ h (s i h , a i h ) + Q ⋆,r h (s i h , a i h ) -2 r h (s i h , a i h ) + max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 F i h (a) ≤ 16H 2 Q ′ h (s i h , a i h ) -Q ⋆,r h (s i h , a i h ) 2 = 16H 2 E Z i h (Q ′ , r) F i h .Here inequality (a) holds since|Q ′ h (s i h , a i h ) + Q ⋆,r h (s i h , a i h ) -2(r h (s i h , a i h ) + max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ))| ≤ 4H almost surely. Notice that {Z i h (Q ′ , r) -E Z i h (Q ′ , r)|F i h } k-1 i=0 is the martingale difference sequence adapted to {F i h } k-1 i=0. Besides, almost surely, we have thatZ i h (Q ′ , r) ≤ max Q ′ h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 , Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 ≤ 4H 2 .Then we immediately get that|Z i h (Q ′ , r) -E Z i h (Q ′ , r)|F i h | ≤ 8H 2almost surely. Thus we can apply Lemma 6 and obtain that for any η ∈ (0, 1/(4H 2 )], with probability at least 1 -δ,k-1 i=0 Z i h (Q ′ , r) - k-1 i=0 E Z i h (Q ′ , r) F i h ≤ η k-1 i=0 Var Z i h (Q ′ , r) F i h + log(1/δ) η ≤ 36H 2 η k-1 i=0 E Z i h (Q ′ , r) F i h + log(1/δ) η .This implies that- k-1 i=0 Z i h (Q ′ , r) ≤ 36H 2 η -1 k-1 i=0 E Z i h (Q ′ , r) F i h + log(1/δ) η ≤ 16H 2 log(1/δ).The last equation is obtained by choosing η = 1/(16H 2 ).We define (Q h ) ρ and (R h ) ρ as the ρ-cover of Q h and R h , respectively. It is direct to have thatQ ρ = (Q 1 ) ρ × . . . (Q H ) ρ and R ρ = (R 1 ) ρ × . . . (R H ) ρ are ρ-covers of Q and R, respectively. By union bound, with probability at least 1 -δ, for all (k, h, Q, r)∈ [K] × [H] × Q ρ × R ρ , we have that - k-1 i=0 Z i h ( Q, r) ≤ 16H 2 log KH H h=1 (|(Q h ) ρ ||(R h ) ρ |)/δ ≤ 16H 3 log KH max h∈[H] |(Q h ) ρ ||(R h ) ρ |/δ . Furthermore, for any (Q, r) ∈ Q × R, there exists ( Q, r) ∈ Q ρ × R ρ such that ∥Q -Q∥ ∞ ≤ ρ and ∥r -r∥ ∞ ≤ ρ. Then we have that k-1 i=0 Z i h (Q, r) - k-1 i=0 Z i h ( Q, r) ≤ k-1 i=0 Z i h (Q, r) -Z i h ( Q, r) .For each term, we have thatZ i h (Q, r) -Z i h ( Q, r) ≤ Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 -Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) 2 + Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 -Q ⋆, r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) 2 .For the first term in RHS, we have thatQ h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 -Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) 2 ≤ Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) + Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) Q h (s i h , a i h ) -Q h (s i h , a i h ) -r h (s i h , a i h ) + r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) + max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) ≤ 4H Q h (s i h , a i h ) -Q h (s i h , a i h ) + r h (s i h , a i h ) -r h (s i h , a i h ) + max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) -Q ⋆, r h+1 (s i h+1 , a ′ ) ≤ 12H 2 ρ.The last inequality follows Lemma 7. Similarly, for the second term in RHS, we have thatQ ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 -Q ⋆, r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) 2 ≤ Q ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) + Q ⋆, r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) • Q ⋆,r h (s i h , a i h ) -Q ⋆, r h (s i h , a i h ) -r h (s i h , a i h ) + r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) + max a ′ ∈A Q ⋆, r h+1 (s i h+1 , a ′ ) ≤ 6H Q ⋆,r h (s i h , a i h ) -Q ⋆, r h (s i h , a i h ) + r h (s i h , a i h ) -r h (s i h , a i h ) + max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) -Q ⋆, r h+1 (s i h+1 , a ′ ) ≤ 18H 2 ρ.Combining the above four inequalities yields thatk-1 i=0 Z i h (Q, r) - k-1 i=0 Z i h ( Q, r) ≤ k-1 i=0 Z i h (Q, r) -Z i h ( Q, r) ≤ 30kH 2 ρ.Therefore, for all(Q, r) ∈ Q × R, - k-1 i=0 Z i h (Q, r) ≤ - k-1 i=0 Z i h ( Q, r) + k-1 i=0 Z i h (Q, r) - k-1 i=0 Z i h ( Q, r) ≤ 16H 3 log(KH max h∈[H] |(Q h ) ρ ||(R h ) ρ |/δ) + 30kH 2 ρ ≤ 16H 3 log(KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 30kH 2 ρ.This implies thatQ ⋆,r h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 ≤ inf Q h ∈Q h Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ ∈A Q ⋆,r h+1 (s i h+1 , a ′ ) 2 + 16H 3 log(KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 30kH 2 ρ.Therefore, we can derive the upper bound on BE k (Q ⋆,r k ).BE k (Q ⋆,r k ) = H h=1 k-1 i=0 Q ⋆,r k h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q ⋆,r k h+1 (s i h+1 , a ′ ) 2 -inf Q ′ h ∈Q h k-1 i=0 Q ′ h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q ⋆,r k h+1 (s i h+1 , a ′ ) 2 ≤ 16H 4 log(KH max h∈[H] N ρ (Q h )N ρ (R h )/δ) + 30kH 3 ρ.We complete the proof.For any fixed tuple(k, h, Q, r) ∈ [K] × [H] × Q × R, we define the random variable. X i h (Q, r) := Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 -(T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 .We define the filtration F i = σ({(s j 1 , a j 1 , . . . , s j H , a j H )} i-1 j=0 ). In the following part, we calculate the expectation and variance of X i h (Q, r) conditioned on F i .E X i h (Q, r)|F i = E Q h (s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 F i -E (T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 F i = E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) + (T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 F i -E (T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) 2 F i = E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 F i + 2E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) (T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) F i = E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 F i + 2E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) • E (T r h Q h+1 )(s i h , a i h ) -r h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) s i h , a i h F i = E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 π i . Var X i h (Q, r)|F i ≤ E X i h (Q, r) 2 |F i = E Q h (s i h , a i h ) + (T r h Q h+1 )(s i h , a i h ) -2r h (s i h , a i h ) -2 max a ′ Q h+1 (s i h+1 , a ′ ) 2 • Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 F i ≤ 16H 2 E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 π i = 16H 2 E X i h (Q, r)|F i . Furthermore, {X i h (Q, r) -E[X i h (Q, r)|F i ]} k-1 i=0 is a martingale difference sequence adapted to {F i } k-1 i=0. Besides, it is easy to obtain that |X i h (Q, r)| ≤ 9H 2 almost surely. Thus, we can apply Lemma 6 and obtain that with probability at least 1 -δ, for any η ∈ (0, 1/(9H 2 )],k-1 i=0 X i h (Q, r) - k-1 i=0 E[X i h (Q, r)|F i ] ≤ η k-1 i=0 Var X i h (Q, r)|F i + log(2/δ) η ≤ 16H 2 η k-1 i=0 E X i h (Q, r)|F i + log(2/δ) η . By choosing η = min{1/(9H 2 ), log(2/δ)/(16H 2 k-1 i=0 E X i h (Q, r)|F i )}, we have that k-1 i=0 X i h (Q, r) - k-1 i=0 E[X i h (Q, r)|F i ] ≤ 8H k-1 i=0 E X i h (Q, r)|F i log(2/δ) + 9H 2 log(2/δ).This implies thatk-1 i=0 E[X i h (Q, r)|F i ] -8H k-1 i=0 E X i h (Q, r)|F i log(2/δ) ≤ k-1 i=0 X i h (Q, r) + 9H 2 log(2/δ).This establishes a quadratic formula ofx 2 -bx -c ≤ 0 with x = k-1 i=0 E[X i h (Q, r)|F i ], b = 8H log(2/δ) and c = k-1 i=0 X i h (Q, r) + 9H 2 log(2/δ). Solving this quadratic formula yields that (b - √ b 2 + 4c)/2 ≤ x ≤ (b + √ b 2 + 4c)/2, which implies that x 2 ≤ (b + √ b 2 + 4c) 2 4 ≤ 2 b 2 + b 2 + 4c 4 = b 2 + 2c.Thus we obtain thatk-1 i=0 E[X i h (Q, r)|F i ] ≤ 2 k-1 i=0 X i h (Q, r) + 82H 2 log(2/δ).We define (Q h ) ρ and (R h ) ρ as the ρ-covers of Q h and R h , respectively. It is direct to have thatQ ρ = (Q 1 ) ρ × . . . (Q H ) ρ and R ρ = (R 1 ) ρ × . . . (R H ) ρ are ρ-covers of Q and R, respectively. By union bound, with probability at least 1 -δ, for all (k, h, Q, r) ∈ [K] × [H] × Q ρ × R ρ , k-1 i=0 E[X i h ( Q, r)|F i ] ≤ 2 k-1 i=0 X i h ( Q, r) + 82H 2 log(2KH|Q ρ ||R ρ |/δ) = 2 k-1 i=0 X i h ( Q, r) + 82H 2 log 2KH H h=1 (|(Q h ) ρ ||(R h ) ρ |) /δ ≤ 2 k-1 i=0 X i h ( Q, r) + 82H 3 log 2KH max h∈[H] |(Q h ) ρ ||(R h ) ρ |/δ .We have calculated the conditional expectation in the LHS and obtain thatk-1 i=0 E Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 π i ≤ 2 k-1 i=0 X i h ( Q, r) + 82H 3 log 2KH max h∈[H] |(Q h ) ρ ||(R h ) ρ |/δ ≤ 2 k-1 i=0 X i h ( Q, r) + 82H 3 log 2KH max h∈[H] N ρ (Q h )N ρ (R h )/δ .According to the definition of ρ-cover, for (Q k , r k ), there exists( Q, r) ∈ Q ρ × R ρ such that max (s,a,h)∈S×A×[H] Q h (s, a) -Q k h (s, a) ≤ ρ, max (s,a,h)∈S×A×[H] r h (s, a) -r k h (s, a) ≤ ρ.Then we can upper bound the errors caused by approximating(Q k , r k ) with ( Q, r). Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) 2 -Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 ≤ Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) + Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) -Q k h (s i h , a i h ) + (T r k h Q k h+1 )(s i h , a i h ) ≤ 2H Q h (s i h , a i h ) -(T r h Q h+1 )(s i h , a i h ) -Q k h (s i h , a i h ) + (T r k h Q k h+1 )(s i h , a i h ) ≤ 6Hρ. X i h ( Q, r) -X i h (Q k , r k ) ≤ Q h (s i h , a i h ) + Q k h (s i h , a i h ) -r h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) -max a ′ Q k h+1 (s i h+1 , a ′ ) • Q h (s i h , a i h ) -Q k h (s i h , a i h ) -r h (s i h , a i h ) + r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) + max a ′ Q k h+1 (s i h+1 , a ′ ) + (T r h Q h+1 )(s i h , a i h ) + (T r k h Q k h+1 )(s i h , a i h ) -r h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) -max a ′ Q k h+1 (s i h+1 , a ′ ) • (T r h Q h+1 )(s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) -r h (s i h , a i h ) + r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) + max a ′ Q k h+1 (s i h+1 , a ′ ) ≤ 4H Q h (s i h , a i h ) -Q k h (s i h , a i h ) -r h (s i h , a i h ) + r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) + max a ′ Q k h+1 (s i h+1 , a ′ ) + 4H (T r h Q h+1 )(s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) -r h (s i h , a i h ) + r k h (s i h , a i h ) -max a ′ Q h+1 (s i h+1 , a ′ ) + max a ′ Q k h+1 (s i h+1 , a ′ ) ≤ 24Hρ.With the above bounds, we can obtain thatk-1 i=0 E Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i ≤ 2 k-1 i=0 X i h (Q k , r k ) + 82H 3 log 2KH max h∈[H] N ρ (Q h )N ρ (R h )/δ + 54kHρ.According to the definition of BE k , we have thatBE k (Q k ) = H h=1 k-1 i=0 Q k h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q k h+1 (s i h+1 , a ′ ) 2 -inf Q ′ ∈Q H h=1 k-1 i=0 Q ′ h (s i h , a i h ) -r k h (s i h , a i h ) -max a ′ Q k h+1 (s i h+1 , a ′ ) 2 (a) ≥ H h=1 k-1 i=0 X i h (Q k , r k ) ≥ 1 2 H h=1 k-1 i=0 E Q k h (s i h , a i h ) -(T r k h Q k h+1 )(s i h , a i h ) 2 π i -41H 4 log 2KH max h∈[H] N ρ (Q h )N ρ (R h )/δ -27kH 2 ρ.Inequality (a) follows Assumption 3 that T r k h Q r k h+1 ∈ Q h We complete the proof.Lemma 6 (Freedman's inequality [3] ). Let (X t ) t≤T be a real-valued martingale difference sequence adapted to filtration F t , and letE t [•] = E[• | F t ]. If |X t | ≤ R almost surely, then for any η ∈ [0, 1 R ] it holds that with probability at least 1 -δ, T t=1 X t ≤ η T t=1 E t-1 [X 2 t ] + log(1/δ) η .Lemma 7. For any reward functions r, r, we have that∀(s, a, h) ∈ S × A × [H], Q ⋆,r h (s, a) -Q ⋆, r h (s, a) ≤ H h ′ =h max s∈S,a∈A |r h (s, a) -r h (s, a)| .Here Q ⋆,r is the optimal Q-value function of r.Proof. According to the Bellman optimality equation, we have thatQ ⋆,r h (s, a) -Q ⋆, r h (s, a) = r h (s, a) -r h (s, a) + E s ′ ∼P h (•|s,a) max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ ) ≤ |r h (s, a) -r h (s, a)| + E s ′ ∼P h (•|s,a) max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ ) .We analyze the term| max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ )|. max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ ) = Q ⋆,r h+1 (s ′ , a 1 ) -Q ⋆, r h+1 (s ′ , a 2 ) ≤ Q ⋆,r h+1 (s ′ , a 1 ) -Q ⋆, r h+1 (s ′ , a 1 ), max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ ) = Q ⋆,r h+1 (s ′ , a 1 ) -Q ⋆, r h+1 (s ′ , a 2 ) ≥ Q ⋆,r h+1 (s ′ , a 2 ) -Q ⋆, r h+1 (s ′ , a 2 ).HereEQUATIONThen we have that ∀(s, a) ∈ S × A,Q ⋆,r h (s, a) -Q ⋆, r h (s, a) ≤ |r h (s, a) -r h (s, a)| + E s ′ ∼P h (•|s,a) max a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -max a ′ ∈A Q ⋆, r h+1 (s ′ , a ′ ) ≤ |r h (s, a) -r h (s, a)| + max s ′ ∈S,a ′ ∈A Q ⋆,r h+1 (s ′ , a ′ ) -Q ⋆, r h+1 (s ′ , a ′ ) .′ = h to h ′ = H with Q ⋆,r H+1 (s, a) = Q ⋆, rH+1 (s, a) = 0 completes the proof. Lemma 8. For a ≥ 1 and ε ≤ 1, when K ≥ 4 log(4a/ε)/ε 2 , we have thatlog(aK) K ≤ ε.Proof. We consider the function f (K) = log(aK)/K and calculate the gradient.f ′ (K) = 1 2 log(aK) K -1/2 1 -log(aK) K 2 .When K ≥ 4 log(4a/ε)/ε 2 ≥ 4, we have that f ′ (K) ≤ 0, implying that f (K) is a monotonically decreasing function in this range. Then we have thatlog(aK) K ≤ log (4a log(4a/ε)/ε 2 ) 4 log(4a/ε) ε = log(4a/ε) + log(log(4a/ε)) + log(1/ε) 4 log(4a/ε) ε (a) ≤ log(4a/ε) + log(4a/ε) + log(1/ε) 4 log(4a/ε) ε (b) ≤ ε.Inequality (a) follows that log(x) ≤ x + 1 and inequality (b) follows that a ≥ 1.C.1 Implementation Details of OPT-AIL Reward Update. As mentioned in Section 4.2, we choose ψ(r) in Eq. ( 2) as the gradient penalty (GP) regularization of the reward model [6] , which can help stabilize the online optimization process by enforcing 1-Lipschitz continuity of the reward model r. Here D I is linear interpolations between the replay buffer D k and expert demonstrations D E .ψ(r) = E τ ∼D I H h=1 (∥∇r h (s h , a h )∥ -1) 2Policy Update. Here we present the implementation details of policy updates. Firstly, to stabilize the training process, we refine the optimism regularization term by subtracting a baseline Q-value function from random policy µ ≡ Unif(A), which has been utilized in [29, 32] . Furthermore, recognizing that initial state samples can be limited and lack diversity, we employ both the replay buffer D k and expert demonstrations D E to compute the Q-value loss, which is a common data augmentation approach and has been validated in many deep AIL methods [28, 15, 56] . Incorporating these two enhancements, we reformulate the Q-value model training objective as follows.minQ∈Q E τ ∼D k ∪D E H h=1 Q h (s h , a h ) -r k h -Q h+1 (s h+1 , π k ) 2 -λE τ ∼D k ∪D E H h=1 Q h (s h , π k ) -Q h (s h , µ) .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 1 and regard the resultant policy as 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.OPT-AIL: Our codebase of OPT-AIL extends the open-sourced framework of IQLearn. We retain the structure and parameter design of the actor and critic from the original framework while employing SAC [17] with a fixed temperature for policy update. We also implement a discriminator with a similar architecture to 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 in Table 2 .We emphasize that for a fair comparison, all algorithms are implemented using the same codebase 2 , with all hyperparameters kept consistent except for the gradient penalty coefficient. Specifically, in OPT-AIL, the gradient penalty coefficient is set to 1 for Cartpole Swingup, Walker Walk, and Walker Stand, and 10 for other tasks. For baselines, the gradient penalty coefficient is always set 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. 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 is 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. NeurIPS Paper Checklist 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.We will not omit log(N (F)) for a function class F in the O notation since log(N (F)) could not be small for many function classes.Here we present the result of BC in the worst case, which is consistent with this paper.3M training steps for Cheetah Run, Hopper Hop, and Walker Run, and 1M training steps for other tasks.The codebase of PPIL is consistent with IQLearn. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The practical algorithm itself is not highly innovative. The idea of running a no-regret algorithm to update the reward function is not new, and using an actor-critic framework for policy updates is also common.
2. The baselines compared are not SOTA algorithms for AIL/IRL. For instance, algorithms like FILTER (Swamy, Gokul, et al., "Inverse Reinforcement Learning Without Reinforcement Learning," ICML 2023) and HyPER (Ren, Juntao, et al., "Hybrid Inverse Reinforcement Learning," arXiv preprint, 2024) outperform IQ-Learn.

Minor issue:

3. For lines 270-272, the idea of using a no-regret algorithm for updating the reward function is not new. It has been explored and justified in previous work (such as Swamy, Gokul, et al., "Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap," ICML 2021).
questions: questions: 1. Is it possible to add experiments comparing with FILTER and HyPER? I understand it is mainly a theory paper, but it would be good to add the latest SOTA algorithms to be the baselines.
2. Can FTRL directly be a justification for using off-policy update for reward function? Like, OGD is all a instance of FTRL but only update the reward function based on the current policy.
limitations: limitations: Yes, the authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The idea and techniques in this paper seems direct given the existing theoretical works on AIL and RL with general function approximations especially [1] and [2].
2. The assumption of low generalized eluder coefficient [2] is from standard RL literature and is directly adapted here, without further explanations or discussions. 

**References:**

[1] Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang, and Zhaoran Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. *Advances in Neural Information Processing Systems 36*, 2024.

[2] Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. A posterior sampling framework for interactive decision making. *arXiv*, 2211.01962, 2022.
questions: questions: 1. When the main theory translates to linear (or linear mixture) setups in AIL, how does the corresponding result compare with the previous arts?
2. Could the authors highlight the theoretical difficulties or novelties that arise from applying the idea of [1] to the setup of AIL?
limitations: limitations: Please see the weakness section and the question section above.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The complexity measure and main idea of algorithm is not entirely novel, which is based on GEC and a series of optimism-based work on general function approximation like GOLF.
- It seems that the paper mainly focus on the value-based hypothesis class and cannot incorporate the model-based ones directly.
- The discussions on errors $\varepsilon_{\rm opt}^r$ and $\varepsilon_{\rm opt}^Q$ is not sufficient (see Questions).
questions: questions: - It is mentioned that one of the motivations of focusing on general function approximation is the implementation of neural networks in practice. How can neural network function class be included in the architecture? What’s the complexity of such classes?
- In the 3rd line of OPT-AIL, a no-regret algorithm is implemented to obtain the reward. Though author provides some explanations, it's still remain a bit confusing to me. Can authors elaborate more on this part, e.g., algorithm, optimization target, a brief recap of theoretical analysis (if these topics are well-dicussed in literature)?
limitations: limitations: I suggest the authors to include more dicussions on the primary techincal difficulties in contribution part while deriving their theoretical results for AIL.
paper_summary: paper_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.
strength_weakness: strength_weakness: - There are many typos. For instance:
- line 12 "near-expert"
- line 43 you say have extended, but [28] is older than [54]
- table 1 it should be "linear mixture"
- line 141 $\mathcal{R}_h$ does not represent a reward class defined in that way
- line 143,149 it should be "realizability"
- line 145 $\mathcal{Q}_h$ does not represent a class defined in that way
- line 190 I think that the value functions should have an hat
- ...

- The authors make many assumptions to solve the problem. In particular, assumptions 1,2,3, as well as assumption 4, which I am not sure how strong it is as structural assumption
- Algorithm 1 requires to keep in memory all the K policies collected so far, which are many according to Theorem 1. Thus, this stuff may be rather inefficient concerning the memory storage.
questions: questions: - why your algorithm has an expert complexity which does not depend, differently from other algorithms, on the state-action space someway?
- At lines 246-248, when you say that your algorithm improves by an order of $\mathcal{O}(H^2)$ over BC, why do you think is so? Because of the structural assumptions that you added to the problem? Moreover, I do not understand why the rate of BC is $H^4$ instead of the common $H^2$.
- at lines 324-325, you say that a promising direction would be to try to achieve the optimal $H^{3/2}/\epsilon$ rate for the expert sample complexity. But who says that this is the optimal rate for the general function approximation setting? Authors [35] demonstrate that $H^{3/2}/\epsilon$ is optimal in the tabular setting thanks to accurate estimates of the transition model. But if you look at [34], authors say that the knowledge of the transition model does not allow to break the quadratic barrier in problems with continuous state space trivially, but have to devise something else. What do you think?
limitations: limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.

Comments: comment: We sincerely appreciate your constructive feedback throughout the review process. We will revise the paper according to your suggestions. We are pleased to know that you appreciate our responses, and we extend our gratitude for your positive score.
Your valuable comments and feedback are deeply appreciated. We are pleased to know that our responses have addressed your questions, and we are committed to incorporating the above answers as we revise the paper. We extend our sincere gratitude for your positive evaluation.
We sincerely appreciate your constructive feedback throughout the review process. We are fully committed to incorporating your suggestions as we revise the paper. We are glad to hear that you recognize the contributions of this work, and we are grateful for your positive score.
Thank you very much for your insightful comments and feedback. We will supplement these experimental results and revise the paper according to your suggestions. We are pleased to learn that our responses have addressed your concerns, and we deeply appreciate your reconsideration of the score.
Thank you for your detailed response and for adding the experiments.

Regarding Q2: I appreciate the additional experiments. The results are quite promising. For interaction efficiency, based on the plot, I would suggest describing the results as "competitive with HyPE, demonstrating more interaction-efficient learning in some environments." As for FILTER, you could try experiments in scenarios where exploration is particularly challenging in your final version, such as antmaze. Overall, I find the experimental results to be strong.

Regarding Q3: I still believe that the point you're making is somewhat known in the field. It might be worth reviewing other papers that use FTRL for reward updates to avoid overstating the novelty of your contribution.

Regarding Q4: Thank you for your response. I would recommend including this discussion in the final version of the paper.

Overall, I think this is a strong theory paper with practical algorithms and solid experimental results. I’d like to raise my score to 7.
I thank the authors for the detailed and precise responses. I decide to keep my (positively biased) score, with (rather low) confidence.
Thank you very much for your detailed answer to all my questions! I still appreciate the contributions of the work and I am in favor of the acceptance of the paper. I have no further questions and will remain my positive score.
I thank the authors for the detailed response and I would suggest the authors to the authors to also incorporate answer in the revised version to better back up the claim in introduction. Besides, I think the difficulties and solution mentioned in answer 5, such as martingale concentration and covering number, is quite standard in RL rather than ``unlike”.  Overall, I am maintaining my original score and remain in favor of acceptance.