Inverse Q-Learning Done Right: Offline Imitation Learning in $Q^\pi$-Realizable MDPs
Authors: Antoine Moulin
Gergely Neu
Luca Viano
Venue: NeurIPS 2025 poster ()
Keywords: imitation learning
primal dual methods
sample complexity guarantees
Primary area: reinforcement_learning

Abstract: We study the problem of offline imitation learning in Markov decision processes (MDPs), where the goal is to learn a well-performing policy given a dataset of state-action pairs generated by an expert policy. Complementing a recent line of work on this topic that assumes the expert belongs to a tractable class of known policies, we approach this problem from a new angle and leverage a different type of structural assumption about the environment. Specifically, for the class of linear $Q^\pi$-realizable MDPs, we introduce a new algorithm called saddle-point offline imitation learning (\SPOIL), which is guaranteed to match the performance of any expert up to an additive error $\varepsilon$ with access to $\mathcal{O}(\varepsilon^{-2})$ samples. Moreover, we extend this result to possibly nonlinear $Q^\pi$-realizable MDPs at the cost of a worse sample complexity of order $\mathcal{O}(\varepsilon^{-4})$. Finally, our analysis suggests a new loss function for training critic networks from expert data in deep imitation learning. Empirical evaluations on standard benchmarks demonstrate that the neural net implementation of \SPOIL is superior to behavior cloning and competitive with state-of-the-art algorithms.

Inverse Q-Learning Done Right: Offline Imitation Learning in Q Realeazze MDPs
Antoine Moulin Universitat Pompeu Fabra antoine. moul in@upf edu
Gergely Neu
Luca Viano EPFL luca. www.wieaannn....mmmmm
Universitat Pompeu Fabra gergely Srrgely.neuggeee neu@gmail. com
Abstract
We study the problem of offline imitation learning Markov decision processes (MDPs), where the goal is to learn a well-performing policy given dataset of state-action pairs generated by an expert policy. Complementing a recent line of work on this topic that assumes the expert belongs tractable class of known policies, we approach this problem from a new angle and leverage a different type of structural assumption about the environment. Specifically, for the class of linear Q" -e-realizable MDPs, we introduce a new algorithm called saddle-point offline imitation learning (SPOIL), which is guaranteed to match the performance of any expert up to an additive error E with access to O( samples. Moreover, we extend this result to possibly nonlinear Q² ""-realizable MDPs at the cost of worse sample complexity
order O(e-t). Finally, our analysis suggests new loss function for training critic networks from expert data in deep imitation learning. Empirical evaluations on standard benchmarks demonstrate that the neural net implementation of SPOIL is superior to behavior cloning and competitive with state-of-the-ar algorithms.
Introduction
In imitation learning (IL), learner observes finite dataset of state-action pairs generated by an expert policy interacting with an environment modeled as a Markov Decision Process (MDP; Puterman, 2014). The learner's objective is find policy that performs nearly well as the expert policy with respect to an unknown ground-truth reward function. This work focuses on offline imitation learning, where the learner cannot collect new state-action sequences from the MDP used for generating the expert's data. In this context, we propose new algorithms that operate under previously under-explored set of structural assumptions on the learning environment.
Recent years have seen a quite significant surge of interest the problem imitation learning, not unlikely due to its relevance to next-token prediction in generative language models (Rajaraman et al., 2020; Foster et al., 2024; Rohatgi et al., 2025). common feature of these recent works that they all make the assumption that the expert data has been generated by fixed policy that belongs to known, finite class of policies and they return policies within the same class. Such an assumption is often referred to expert realizability and can be formally stated as follows.
Assumption (Expert realizability). The learner has access a function class II that contains the unknown expert policy ne. that is, such that mg E II.
Several clean and elegant results were proved under this assumption, in particular showing the existence conceptually simple algorithms achieving tight upper bounds on the sample complexity of finding good solutions, and lower bounds demonstrating the near-optimality of these algorithms under said assumptions. These bounds typically depend on measure of complexity of the policy class (as measured by, say, its covering number). However, further scrutiny reveals that these assumptions
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

may not always be verified or even reasonable: in many cases of significant practical interest, there no reason to believe that the expert policy may be easily modeled within a simple and tractable policy class. For instance, in the popular use case of learning from human feedback, it is arguably quite unlikely that data would be generated in consistent, systematically predictable way that can be modeled as simple policy mapping states to actions. Indeed, human behavior can be nonstationary. irrational, or even be influenced by unobserved confounders not captured by the state representation. We address these limitations by exploring an alternative framework for imitation learning, which reasons about the structure of the value functions of the policies used by the learning algorithm itself, as opposed to making assumptions about the structure of the policy followed by the expert.
Furthermore, the sample complexity guarantees in Rajaraman et al. (2020); Foster et al. (2024); Rohatgi et al. (2025) scale with log [IT (assuming II" is finite), meaning large policy classes, potentially necessary to realize the expert, lead to deteriorated guarantees. Additionally, the con- sequences of misspecification, i.e,, Ty É IT. are often severe. For instance, Rohatgi et al. (2025) demonstrated that if the policy class I1 misspecified, then computationally intractable to learn arg min DH (1PT, ). the best in-class policy under the Hellinger distance, in offline manner. However, this theoretical intractability under misspecification seems at odds with practical scenarios, such as training large language models via next-token prediction (a form of offline IL), which perform well despite the expert policy (derived from human-written text) likely not belonging to any reasonable policy class II
To address this apparent discrepancy, we initiate the study of offline IL by leveraging structural assumptions about the MDP rather than relying on expert realizability. For example, in language tasks, structural assumptions might involve deterministic, tree-shaped MDPs. roboties, one might assume that next states are determined by compact feature representations of current state-action pairs. More generally, we consider MDPs where the action-value functions of a subset of policies can be written as a linear combination of features known to the learner. Such MDPs are referred to as linear Q* rrellzzabe MDPs, a class that has been central to recent works in reinforcement learning theory (Weisz et al., 2023; Mhammedi, 2025; Tkachuk et al., 2024). Our primary contribution is to show that, for this class of MDPs, it is possible to develop algorithms that guarantee to output a policy performing arbitrarily close to the expert policy without imposing expert realizability.
The algorithm is based on simple primal-dual formulation of the problem of imitation learning, which characterizes the solution as the saddle-point of a convex-concave objective function. The primal variables correspond to policies in the MDP and the dual variables to Q-functions, which motivates very simple saddle-point optimization algorithm for imitation learning: in a sequence of rounds, the primal player (the actor) picks a policy and the dual player (the critic) picks a Q- function, respectively trying to minimize and maximize the objective. We accordingly call the method SPOIL, standing for Saddle-Point Offline Imitation Learning. In the case of linear function approximation, both update steps of SPOIL can be performed very efficiently (in time linear in the feature dimension). For general function approximation, the Q-function updates can be performed by solving simple linear optimization problem, which is straightforward to solve in practical scenarios. When instantiated with neural networks, empirical experiments show its performance is competitive with (and in some cases superior to, e-g., behavior cloning) state-of-the-ar offline imitation learning algorithms. Interestingly, our algorithm shares good degree of similarity with the state-of-the-- method of Garg al. (2021) called IQ-Learn, which is also derived from primal-dual perspective. We discuss these similarities in depth and argue that SPOIL provides a superior solution to the IQ-Learn objective (at least inasmuch it is more amenable to theoretical analysis).
To the best of our knowledge, this is the first result showing that leveraging structural assumptions of the underlying MDP can guarantee matching the expert performance as the number of expert transitions goes to infinity without imposing any form of expert realizability assumption. For clarity, we compare our contribution with existing results in Table 1. We denoted NC (1:llle) the c-covering number of the function class Q (see Theorem 2), and 7. the number of trajectories needed to make the difference in total expected return between the expert and the output policy smaller than
Notation. We use A(Z) to denote the simplex over the countable set Z. Given two proba- bility distributions p, q E A(Z), we denote the Kullback-Leibler divergence as DKL (p.4) = p(a) Essz P(z) log 7(2) We denote (+-) the inner product between two finite-dimensional vectors, and ||-II the Fuclidean norm. We denote 2((K)) the uniform distribution over the set [K] = (1,..., K). The Euclidean ball of radius R > 0 centered at the origin is denoted as B(R).
2

---

Table 1: Comparison with related algorithms. We denoted the class of deterministic linear experts as I lin { 30 E (Bp),, sT+) arg maxxx54 (6, : a))). and an arbitrary policy class as IT.
We also define W max
Ne.
Emiss
gin (H(T,, pPt), and Ō Ō
Algorithm
Structural assumption
Avoids expert realizuhility
Infinite borizon
Expert class
Expert Traj. (1)
BC with loss (Foster et al., 2024)
IF
BC with 0-1 loss (Rajaramun et al., 2021)
Bacatedingl.ooss (Robatgi all,, 2025)
with misspecification error O1N log(W (esis)
IF
8r [e
Projection (Abbeel und Ng. 2004)
Linear reward Known transitions
(1-5)t03
XMAL (Syed and Schapire, 2007)
Linear reward Known transitions
lantch (1-5)'
SPOIL.
Linear Q realizabiili
Ö
(Theorem
SPOT1.
n" ""-realizability
(Theorem
(1-7)-2
2 Preliminaries
We begin by introducing the problem of offline imitation learning in discounted MDPs together with the assumptions we will consider throughout the paper.
Markov decision processes. We formalize the learning problem in a discounted MDP M (X,A, r, P. y, vo), where X is the state space which we assume finite but too large to be enumerated, A is finite action space with A actions, X' A + [0, 1] is the unknown reward function, P: XxAAA A(X)) is the unknown transition kernel, 7 E [0. 1) is the discount factor, and 1/ E ( is the initial state distribution. For any state-action-stann triplet ax.,,, P(x' x. a) denotes the probability of landing in state x' after taking action a in state x. A stationary policy (or simply policy) :: X > ((A) is mapping from states to distributions over actions. The interaction of a policy with the environment M unfolds as follows: an initial state Xn ~ 1o is drawn, and for each subsequent time step h > O, an action A. x(- Xx.) is taken, a reward r(Xn, An, is received, and the agent transitions to new state X ~ P(. Xx. As). We denote 1p" the resulting probability distribution over trajectories, and E" the corresponding expectation operator. For any state I E X, we define the state value function of the policy as v=xx)= E"
Σn r",, An) Xo = z]. Analogously,
we define the state-action value function Q* a) E [En ae ( An) Xo x, Ao a].
The value functions are tied together via the Bellman equations
(*)(
Σ (aa (x,)), and (=(x,a)= r(z, a) + Σ P(x' (al12,a)VV (z))) a
xe
Additionally, will sometimes use the notation Q(x,, x) to denote E. <aa|=)())))))) π and any function Q: X x A A-R. R. Note that this notation allows us to write V*(x)= Q" T). Any policy induces an occupancy measure μr" E A(X A) over state-action pairs, defined as the discounted total expected times that each state-action pair is visited by policy æ. The same quantity defined for states is called the state-occupancy measure and is denoted as " A(x). For any state-action pair (x., a) E X x A, they are respectively defined as
a) for any policy
(x) = (1 -
APp"XA = =], and n (x, a) = (1 (1-7)
AP=
h PTT
A = x, A, a),
h=
and they are related to each other by the conditions (sometimes called "Bellman flow conditions")
n (zxx)= = Σ P(x1 al (x' a') (2)
(1)
3

---

Notably, these definitions and the flow conditions remain valid for general dustory-dependee policies that may take the entire history of state-action pairs each action An. Finally, we let p² (1 E) [_h=o rX,,,, AA) stand for the normalized expected return of a (potentially nonstationary) policy я. The following useful result, commonly called the performance-difference lemma (Kakade and Langford 2002, see also Eq. 7.14 in Howard 1960), gives useful expression for the performance gap between two policies.
X,, into account when selecting
Lemma 1. Let π be a stationary policy and n' be any policy. Then,
p" p" = (X.A))o (X) VT (X))
Note that this lemma is generally stated for stationary policies, but we will find it useful later to use with general -istory-de policies. We provide the straightforward proof in Appendix B.1.
Imitation Learning. We consider the problem of offline imitation learning. Given dataset DE = { {Xg, i=
TE of state-action pairs sampled from an expert policy's occupancy measure 1 objective is to design an algorithm, Alg, that produces policy gout satisfying
E
out
S
(2)
The algorithm is not allowed any further interaction with the expert policy or the MDP M and only has to work with the record of state-action pairs contained in the data set. As stated in the introduction, we aim to achieve this without imposing expert realizability. Instead, we consider the following structural assumption on the environment.
Assumption 1 (Linear Q*-realizabilityy) Let Ba, B > 0. Given a known mapping :: X A + Red consider the policy class Ilin defined as follows
exp 11 En (p(x,, a), 0zi)
Imn (TE((A)* 3((k))K]K] B( x() ΣrEA exp EK (1/(z b), On>)
For any policy π E Imm there exists vector 0F B(Ba) such that for any state- action pair (z, (z) = (p(x,a), Besides, assume sup=,a (1ı((x,)) a)ll I B.p and supz,a SuPoess (p(z,a),0) S -
Notice that we need assume only linearity of the state action value function for the class of softmax linear policies Ulin- In contrast, prior works on linear QT (TTreelizzblle MDPs (Weisz et al., 2023; Mhammedi, 2025) require the above assumption hold for all Markov policies. Moreover, we highlight that we potentially have that I therefore we do not require realizability of the expert state action value function.
We will also consider the general function approximation setting, where the action value function of any policy
be represented by some function class Q C XxA.
Assumption 2 (Q" (Q"-realizability). An MDP is said Q -rerllzzallee if there exists a function class Q C X such that for any policy x E Ill defined as
exp exp(1EI Qx(2,a))
Il
T TEA(A)* 3(QK) C <[T(((=)=
EveA exp exp(( ( S
it holds that Q" E Q, and for any Q E Q 1101 S 1
For this assumption to make sense, we typically require the function class Q to have bounded capacity. We quantify this via covering numbers, defined as follows.
Definition 1 (Covering number). Let (M, d) be metric spuce, K be subset of M, and e > 0. A set C.(K d) is an e-covering of K for any x E K, there exists y E C. (K, d) such that d(x,, y) S c. The covering number of K, No d). is the minimum cardinality of any such covering of K.

---

3 Primal-dual offline imitation learning
In order to introduce our main algorithmic idea, we define the following objective function:
[ Q) = E (( (XX,)) - x(x,
where we denoted Q(X, -7 E < (x) (Q, A Our main observation is that the main objective function we consider can be rewritten in terms of this function as follows:
Th
[TT; Q*) suPqee (TTQQ)
This suggests good policy π TH may be found by solving the saddle-point optimization problem min, supqee [(T;; Q). Indeed, if one is able to produce policy π satisfying suPoe o [( Q) S E. then the above incquality implies that the suboptimality of n as com- pared to Tg. will also be at most
Inspired by this observation, we set out to design an incremental primal-dual optimization algorithm to approximate the saddle point of the function L. In each iteration 1, ........ K, the algorithm performs two updates: primal update that corresponds to policy updates aiming to minimize L, and a dual update that computes action-value function estimates and aims to maximize L. Following a common terminology in reinforcement learning, we will sometimes refer to the primal updates as actor updates and the dual updates as critic updates.
In order to turn these insights into practical algorithm, we define the following empirical estimate of the objective function L:
((T: - (O
For a fixed Q and и,, this clearly an unbiased estimator of L. In line with the derivations above, we choose critic and actor updates respectively
Ta ( Qk E arg [(MM: Q), and Ta+I x) E Ta(a' z))nQu(2,0))" QEQ
En'e
where 1) > O is a learning-rate (or stepsize) parameter that modulates the strength of the policy updates. After performing K updates, the algorithm chooses random index / uniformly on the integers in [1. KT. and returns π gour = πy. We refer to this algorithm as Saddle-Point Offline Imitation Learning (SPOIL). This algorithm design is justified by the following simple error decomposition that lies at the heart of our main results.
Proposition 1. Let (T) supQee
[(T:: Q) L(;;; 0) The oulput of SPOIL sutisfies
K
2 K
E
B[ Qx) +
(x+))
R=1
Proof. The proof simply follows by noticing
p
E[L(TE x*=
1
[(TRi Q*x))
E (T(((T))]
K
K
K k=1
K
K [[
K Σ B[A(Te)]
E
Qx)
[x)
ElLITASS 2+) +
A=1
where we have used the definitions of A and Qs in the first and second lines, respectively.
The first term in this decomposition corresponds to the regret of the policy player æ against the comparator strategy т.. and can controlled with probability via standard tools of online learning (as found in the excellent books of Cesa-Bianch, and Lugosi 2006 and Orabona 2023). The second term measures the estimation error of the objective function L uniformly over the space of action- value functions Q and along the policies played by the algorithm, and can be controlled with high
5

---

probability via standard concentration arguments. Altogether. the proposition suggests that SPOIL will return a good policy if these estimation errors can be bounded reasonably- fact we will formally show in the next section.
Before stating our performance guarantees for the concrete settings we consider in this paper, we pause to point out a peculiar connection between the algorithm described above and the inverse Q-learning (IQ-Learn) algorithm of Garg al. (2021). While motivated using completely different arguments, the saddle-point objective function optimized by IQ-Learn is nearly identical to our function L: after removing can verify using the flow constraint (Eq. 1) that their function J is identical to our L. Ultimately, Garg et al. (2021) draw different conclusions from this saddle-point formulation, and propose to solve it by computing Te = arg min, [Q) and optimize the dual function g(Q) min, [(T; Q). This function, however, can be highly nonsmooth and difficult to optimize, which is why IQ-Learn needs to heavily rely on regularization both in π and Q. In contrast, our algorithm can be seen as trying to optimize the primal function I f((r) = maxq [(T;; Q) in terms of the policy x, which can done in a stable way by incremental policy updates. Additionally, as Proposition I clearly reveals, optimizing the primal objective allows us to directly reason about the performance of the output policy. In contrast, we do not see clear way to do this for the dual objective optimized by IQ-Learn.
and setting their reward regularizer to zero, one
Furthermore, we also note that SPOIL shares similarities with the algorithm AdVIL proposed by Swamy et al. (2021). Specifically, both SPOIL and AdVIL consider the same objective & but the two methods differ in their proposed algorithmic solutions and analytical approaches. Notably, Swamy et al. (2021) employed simultaneous gradient descent-ascent updates that made little use of the specific problem structure, whereas we consider an asymmetric scheme where the policy player uses mirror descent and the Q-player plays the best response. Therefore, our approach is more akin to minimizing the function + maxqeo [(T,, Q) rather than using a primal-dual scheme. This is an important difference since Proposition I makes evident that the best response update of the Q player is crucial for our analysis.
In what follows, we instantiate SPOIL in two settings of particular interest, depending on the Q- function class being used. We first provide a set results for linear function approximation (where the algorithm is easy to implement and analyze) and for general function classes (where implementation and analysis are both less straightforward). We also discuss the convex case in Appendix B.8.
3.1 SPOIL for linear function approximation
We first provide a set of guarantees under the assumption that the function class is linear in some known features that realize the action-value functions of all softmax linear policies π as linear combinations (see Assumption 1). In this setting, the actor and critic updates both simplify. For the actor, notice that the policy update can be rewritten as TT(a x) xx e Et (a.a), which only requires storing Σ Q; in memory. For linear function approximation, this means that it suffices to maintain a single d-dimensional vector 0,_ = Σ 0, in memory and update it incrementally after each critic update. As for the critic update itsclf, notice that the objective function L and its empirical counterpart can be rewritten in terms of the gap between the eeature-expectation vectors
1 TE
g+ Ex (x(X, A) x0( (0,Xmx)), mx)) and Øk
>
(x At)
oo( mx))
Te
When considering linear functions Qo: (z, a) + (4(x, a). 0). the objective can be written as [(TEE; Qv) = (0, and [( Q0) = (0, (0.m))
and the critic update can be simply written as 0₂ = arg m3 (Ba) (8. 9k). which is trivial to compute. All in all, both actor and critic updates can be performed efficiently while only working in d-dimensional Euclidean space. The following theorem provides our main result for SPOIL.
Theorem 1. Let Assumption hold. Run Algorithm 1 for K
iterations, with a learning 2
[1 -1-
rate 1) = - (1-r) 2og A/K, and T. = O (1= log
B.B.AA [1-7]s
samples collected by any
expert policy ng. Then, the output satisfies E E[p jm ((E)

---

Algorithm/ SPOIL with linear FA
Algorithm SPOIL with general FA
Input: Number of expert trajectories Tu. learning rate 7,. number of iterations K.
Input:
Number of expert trajectories Te, learning
rate 1,, number of iterations K.
Initialize: On= O. uniform policy mo-
Initialize: Qo = O, uniform policy no.
For k = -12...... K:
For = 1,2...... K:
1. (a x) x TT-1(a (a x))=ke(aaa))0 1),
1. TT. ()) x I x)) 1(2.a)
2. 9h = TE E (x(Xg, At) - -x(XE, Rx)).
2. Qk E arg max [(TTK Q) QEO
Bg
3. 0% = arg max (0. gk) 0:110|| Bg
Tk.
Output: c. = TT, where ~ ((K)))
1
Output: nott = TI, where! I ~~ ((((K)).
The proof is in Appendix B.5. It is important highlight that assumptions made concerning the expert policy. In particular, we do not require knowledge of a class II realizing the expert policy and a consequence the bound on Tr does not scale all with complexity measure of IT.. This is in stark contrast with the theoretical guarantees for behavioural cloning (e.g.. Agarwal al., 2022, Chapter 15, and Foster et al., 2024) which show bounds on the expert samples scaling with log [114| (or the log covering number for continuous classes). It follows that no matter how complex the expert policy is, SPOIL suffers only the complexity of the environment (i.e., the feature dimensionality d). Before moving to the next section, we emphasize that for consistency with the literature, Table reports the number of expert trajectories required guarantee that the difference between unnormalized returns, (1 - 7) "E pa "]. is bounded by O(s).
3.2 SPOIL for general function approximation
For more complex Q reareiaize MDPs, we analyze the version of SPOIL given Algorithm 2. Notice that the updates can no longer use the linear structure of the value functions, and thus the critic update cannot be computed in closed form. Nevertheless, the algorithm remains well-defined, and satisfies the following performance guarantee.
Theorem 2. Let Assumption hold. Run Algorithm 2 for K 2 A iterations, with a learning (1-7)'E2
rate = (1- 7) /2 log A/K and T3 = =0( log A (111(11)))) (1-7)*a4 log e(1->) (x)((_1))12)) samples collected by any
expert Tu, where g¹ = (8V2K3/22 log A) Then, the output satisfies TE [[ - -p"""t = O()).
There are two important remarks for the nonlinear extension. First, the maximization of Z(TT Q) with respect Q is no longer available in closed form and it might not even be concave optimization problem depending on the choice of the function class Q. Therefore, computational efficiency cannot be ensured. Nevertheless, the form of the objective function remains very simple in terms of Q, and is arguably easier to optimize than other popular objective functions that are routinely optimized within deep RL with good empirical success (e.g., the objective functions appearing in Mnih et al., 2015) and deep IL. (Garg et al., 2021). Secondly, the expert sample complexity bound degrades from O( 2) achieved in the linear case (E=4)) in the nonlinear case due to the higher complexity of the policies produced by the algorithm (which results in a larger covering number of the policy class as highlighted in the proof sketch included in the next section).
4 Analysis
In this section we outline the proof of our two main results. Both proofs are based on two key steps which are self-evident from Proposition 1. The first one consists of a regret analysis show that ΣK _ L(Tr; Qx) is bounded sublinearly in K. At a high level, the proof makes use of a classic technique of decomposing the "global" regret into the average of "local" regrets in each MDP state, first proposed by Even-Dar et al. (2004, 2009) and used in numerous other works (e.g., Abbasi- Yadkori et al., 2019; Geist et al., 2019; Lan, 2023; Moulin and Neu, 2023). In proving this result,
7

---

little care is needed in handling the potentially nonstationary nature of the expert policy. We circumvent the issue by using the performance difference lemma and controlling the regret each state against the stationary comparator which induces the same state-action occupancy measure of the expert. Formally, we have the following bound, which we prove Appendix B.2.
Lemma 2. For any k and any state-action pair (z, a), consider the sequence of policies starting with as the uniform policy and updated as TK+1(a) x) X T Ta(a (ellz)ee z))""Q(zz.a) for some function Qk: X A R such that [Quilo I 1- Then, Σ ((TTK Q+) I log A
nk
2(1-))²
This lemma applies to both the linear and nonlinear settings. The next and final step of the analysis is to establish concentration of the empirical objective and bound A ( for each k. The main challenge in this step is the correlation between the iterates {TT& /= and the expert dataset. This can [
be handled via a uniform bound over the policy class to which all the algorithm iterates belong to. Importantly, this class is much smaller than the class of all policies, and allows to make massive sample-comples complexity savings as compared to methods that need to control estimation errors associated with arbitrary policies. We provide the technical details separately for the linear and nonlinear cases.
4.1 Linear function approximation
In order bound the estimation errors ( apply covering argument over the class of linear softmax policies. We have the following result.
Lemma 3. Let {TR]RE(K) be the sequence of policies generated by Algorithm and let (TTR) be defined as Proposition Then, with probability least 6, it holds that for all k E [K]
2 + 32 32K
( S K
+ +4
log
(1-7))=
(1 71-7)0
We defer the proof Appendix B.4. We can use the above result to sketch the proof of Theorem 1.
Proof sketch of Theorem 1. Using Lemma 2 with 17 (1 11 /) log
K and dividing by K, we
obtain that $ Ek [(TMi Qk) I V (1-ク)**
2log
Therefore, setting K
2 A (1-7) guarantees
R Σ [(TE; Qx) S 8. Then, using the high-probabilityy bound in Lemma 3 and the fact that K-E A(Te) a random variable bounded by 2(1 - 7) almost surely, we obtain the follow- ing expectation bound which holds for all 6
1 K E[A(T K
Bg Ba
+ 25
+C (1- PT log
(1 (1 (1-7))277 28
1-
1=11
for some C E IR. Noticing that the choice of parameters ensures S b and setting d = <(1
and Te (1- log Bg By this bound implies that & K [[ < 4e. Invoking Proposi- (1-7) tion 1, we conclude that EE R0= p" 1= < 5c. The full proof is in Appendix B.5.
Odd
4.2 General function approximation
The proof for the nonlinear setup follows the same conceptual steps but requires more general concentration result for the objective function. Namely, the following lemma is the general counterpart of Lemma 3. The feature dimension d appearing in the linear case is replaced by the complexity (as measured by the covering number) the policy and value function classes containing the iterates.
k= denote the iterates produced by Algorithm 2, and let (MT. be defined in Proposition Then, with probability at least 1 8, holds that for all [K]
Lemma 4. Let Q XxA denote an arbitrary class, {
8(K + 1) log
2N (2, 11.11-1))/6
A A(TR) S +
K
(1 ---7) 2
8

---

The proof is in Appendix 6.6. Note that in the general case, the complexity of the policy class can increase linearly with the number of iterations K (see Lemma 7). On the contrary, in the linear case. the policies generated by Algorithm 1 are parameterized by d parameters and only the magnitude of these parameters increases with K. With this lemma, we present the proof sketch of Theorem 2.
Proof sketch of Theorem 2. Applying the decomposition in Proposition 1, the regret bound in
Lemma 2, the concentration in Lemma 4, we obtain E E[p"E -p=0"1
Ō J V + k Setting
K- = (s(-)) and TE = Ō(s-)), we get R. T p=""] e. The full proof is in Appendix B.7. n
5 Numerical experiments
We conduct experiments to verify that we can efficiently imitate complex experts in linear Q" environments, and can achieve massive improvements over behavioral cloning with large policy classes.
To investigate this, we consider a randomly generated large linear MDP (a special case of linear Q -eerealizablle MDP) with | = 500 and A = 1000 but with a small feature dimension d 7. We instantiate two experts. The first expert is trained to be the optimal softmax linear policy in this environment. This policy is parametrized by only d parameters and can be realized by the class of softmax linear policies defined in Assumption 1, denoted I here. In addition, we consider the second expert, which belongs to the class of three-layer neural networks denoted by N This expert was trained to minimize the KL divergence with respect to the linear expert. As evident from Figure 1, algorithm SPOIL performs well for both experts. This is in perfect agreement with the theory which provides a sample complexity bound that is independent of the expert policy class. On the other hand, behavioural cloning (BC) struggles with the complexity of the neural network expert policy class, and performs much worse. This is despite the fact that the dataset perfectly satisfies the realizability condition required by BC. This clearly demonstrates that complex behavior policies may indeed be problematic for BC to deal with, and we expect that such issues may also cause real performance drops in practical applications as well. Notice that in this experiment, SPOIL outperforms BC because the environment complexity is much lower than the policy class complexity. For fairness, we point out that the opposite situation is not unusual in RL. and II.. In that case, it is reasonable to expect BC to be superior to SPOIL.
Tg E II
70
Return
65
60
SPC11
55
32
250
500 Epochs
750
1000
gg E NN
68
Return
64
60
56
52
0
250
500
750
1000
Epochs
Figure 1: Experiments with simple and complex experts. Curves are averaged across 10 seeds.
5.1 Continuous states experiments
We run the general function approximation version of our algorithm in continuous-state environments from the gym library (Towers et al., 2025). In particular, we consider the environments CartPole-vi. Acrobot-vi and LunarLander-v2 where the expert is trained via Soft DQN. We use the expert data provided in the code base of Garg et al. (2021). The learner aims at imitating the expert performance given as input a variable number of expert trajectories. In order to make the task more challenging the trajectories are subsampled each 20 steps in CartPole-vi. Acrobot-vi and each 5 in LunarLander-v2. We compare the performance of the best policy found by each of these algorithms as a function of the number of expert trajectories given as input. In practice the maximization arg maxqeq [( Q) is approximated by performing a gradient ascent step. On the other hand, the actor update is approximated via Soft DQN (Haarnoja al., 2017). In Figure 2,
I 'Code is available at: https: //tggggttbbb../////// wwweeehu....mmattaaaeeoeea
"Thi is common practice in IL experiments (see, e.g., Garg al., 2021).

---

CartPolerl
Aerobot-v1
Limeraaderer2
300
Total Rebura
500+
Return
1000
Total Return
200
400+
200
100
300+
300
200-
-400
100
100-
-500
-200
6
10
4
10
4
6
10
Expert Trajectorios
Expert Trajectorics
Expert
Trajectories
Figure 2: Experiments in continuous-state domains. Curves are averaged across 10 seeds.
can see that SPOIL performs comparably to the state-of-the-arr algorithm IQ-Learn (Garg al., 2021) and improves upon BC (Pomerlcau, 1991; Foster et al., 2024) and P²IL (Viano et al., 2022).
6 Conclusions
In this work, we proposed analyses that leverage structural assumptions on the MDP without requiring trajectory access. This is made possible thanks to a novel regret decomposition that shifts the focus from updating reward sequence based on expert data to updating a sequence of state-action value functions. To the best of our knowledge, these are the first rigorous theoretical guarantees for IL methods that learn state-action value functions from expert data, a technique popularized in practice by Garg et al. (2021). Among the many potential ways to extend and improve our work, we highlight two possible future directions below.
Better rates in the general case. The most interesting immediate question that one can ask about our result the ((=-t) scaling featured in our general bound is improvable under the conditions we assume. As a first step, we show an improvement for the case of convex class Q in Appendix B. 8.8. However, we believe that substantially different algorithmic and analytic ideas would necessary to answer this question for non convex classes, but we also think that our primal-dual framework provides a good starting point towards making such improvements. Furthermore, we would be curious to investigate appropriate notions of misspecification that our algorithm can deal with. It can be easily shown that requiring Q -"-realizability only up to a worst-case additive error of order Eapprox would incur the same additional term in the error bounds, but we believe that this assumption is too strong to warrant interest and we did not include an explicit statement. A much more interesting question is if this approximation guarantee would only be required to hold locally in the state-action pairs visited by the expert.
Learning from features only. In the case of linear function approximation, the current approach critically relies on observing the expert state-action pairs to compute the vectors {āx k= It would be interesting to check if an alternative algorithm can achieve the same guarantees by only observing the expert feature vectors instead. Another related direction is to efficiently imitate an expert from state-only trajectory given trajectory access to a linear-Q" realizable MDP.
Finally, let us remark that all previous theory work has focused either on imitation learning with additional trajectory access to the environment, both in tabular MDPs (Shani et al., 2022; Xu et al., 2023) and with additional structural assumptions (Liu et al., 2022; Viano et al., 2022, 2024; Moulin al., 2025), or learning based on offline data only but under structural assumptions about the policy class used by the expert (Rajaraman et al., 2021; Swamy et al., 2022; Foster et al., 2024; Rohatgi al., 2025). The first of these assumptions clearly more restrictive than what we have considered in this work, and we have pointed out potential issues with the second set of methods when the policy class is exceedingly complex. This is not to say though that we consider our approach strictly superior to policy-based based IL methods: as is often the case in RL, there is no single approach that dominates all others all problems, and sometimes policy-based methods are more suitable for the job than value-based ones. Thus, even if our approach is not the ultimate answer to all questions in imitation learning, our results show that one potential alternative to consider in situations where other methods fail.
10

---

Acknowledgments and Disclosure of Funding
The authors wish to thank Emmanuel Esposito for suggesting to look the convex case and Akshay Krishnamurthy for an insightful discussion about our work. Luca Viano is funded through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. Gergely Neu and Antoine Moulin are funded via European Research Council (ERC) project, under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 950180).
References
Yasin Abbasi Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz. Politex: Regret bounds for policy iteration using expert prediction. In International Conference on Machine Learning (ICML), 2019. URL https: https::/ttocceeeeee httpp:s////occedinggs wwapingss.......eeeeeeeeee.eeeee press/ v97/lazic19a 19tmmmml.
Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learming (ICML), 2004. URL httpp::/iiaal..c//ooffeeeeeeeeee http///onffeenee///// /004/ proceedings/ http//aappaa/aa/eeeeeeeeeaaaaaaa 335 .df.
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and gi github.io.
algorithms. 2022. URL
Adam Block, Ali Jadbabaie, Daniel Pfrommer, Max Simchowitz, and Russ Tedrake. Provable guarantees for generative behavior cloning: Bridging low-level stability and high-level behavior. In Advances in Neural Information Processing Systems wtwpo/ceeediinnneuriiieeeeeeeeee wwt.rippp.cpppppppppccppppp lalllpppprleeeee www.fflleaaaaeeee /011e//paper/222// html.
(NeurIPS), 2023. URL 2tt.:99000b22111128aa00000033330
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolas Espinosa Dice, Sanjiban Choudhury, Wen Sun, and Gokul Swamy. Efficient imitation under misspecification. In International Conference on Representation Learning (ICLR), 2025. URL https://openreview
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. cision process. In Advances in Neural Information Processing Systems (NIPS). MIT Press, 2004. URL https://papers.eee nips.
Experts in a markov de-
421 222b3a662444922ddd0661666660 www.sbbbbbbtttttttt..... html.
Eyal Even-Dar, Sham. M. Kakade, and Yishay Mansour. Online Markov decision processes. Mathe- matics of Operations Research, 2009. URL https://wwet jstor. org/ arg/stable sttsstaa/////eeeeee 4/00e//455
Dylan J Foster, Adam Block, and Dipendra Misra. Is behavior cloning all you need? understanding horizon in imitation learning. Anmual Conference on Neural Information Processing Systems (NeurIPS), 2024. URL https: hww.//vpnneeeeeeeeoeoeeee wwtp://oooooiddddddddaaaoa.eaaaa
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning, 2018.
00805.
Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, Mathieu Geist, and Stefano Ermon. IQ-learn: Inverse soft-Q learning for imitation. Advances in Neural Information Processing Systems (NeurIPS), 2021. URI. https: htaps:///rxxii /arxivvv... prrg/bss/2100 12142. Note:
Read arXiv version for correct version and complete author list.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A Theory of Regularized Markov Decision Processes. In International Conference Machine Learning (ICMI., 2019. URL https: //proceedings. mlr. ppwss/v97/geseee /wistt//gei htmm.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning (ICMI), 2017. URL https: sttpss//proceediingg mlr,
wwt.:/essw..rpr.eeeeeeeeeeeeeeee prres/v70/haarmng html.
11

---

Ronald A Howard. Dynamic programming and Markov processes. John Wiley, 1960.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning (ICML), 2002. URL https://homes cs. washington,
aoarl. pdf.
Diederik Kingma and Jimmy Ba. Adam:
method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2014. URL http::////a wttpa////or/a//o/////////a/ss/// ab11/11.. 6980. Note: Read the up-to-date arXiv version.
Guanghui Lan, Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programminng 2023. URL https: h//link.spring...
Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. Learning from demon- stration: Provably efficient adversarial policy imitation with linear function approximation. In International Conference on Machine Learning (ICML), 2022. URL https://proceeding mlr. wwt.:ppressv/////// 1al/62//ll22... html.
Zakaria Mhammedi. Sample and oracle efficient reinforcement learning for mdps with linearly- realizable value functions. In Conference on Learning Theory (COLT), 2025. URL https: //proceedings.. wwt.igg..m.....reeeee (atess//211/haammeeii
html.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Antoine Moulin and Gergely Neu. Optimistic planning by regularized dynamic programming. In International Conference on Machine Learning (ICML), 2023. URL https::/ mlr. pptss//2222momulnnma in23a. html.
Antoine Moulin, Gergely Neu, and Luca Viano. Optimistically optimistic exploration for provably efficient infinite-horizon reinforcement and imitation learning. In Conference on Learning Theory (COLT), 2025. URL httttts:: http::/eds////oeeeepeeeeeme mlr.. wwwpss/veev /22////99111111/ wewoouinn5a.... imouiin25a.hhml. html.
Francesco Orabona. A modern introduction online learning, 2023. URL https://arxivv org/ abs/1912. 13213.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep lcarning library, 2019. URL attps://aet attpv..ivvvv///vv org/ abs/aass/11../// 01703.
Dean A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88-97, 1991. URL https://www .ii. cmu. edu adu/pub http//uu_ffeeeee fwl.ff/llpbpbl
1et___991___111 1.fff
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Progrumming. John
Wiley & Sons, 2nd edition, 2014.
Nived Rajaraman, Lin Yang, Jiantao Jiao, and Kannan Ramchandran. Toward the fundamen- tal limits of imitation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020. URL htttss:/ppocceedinggg. 4brer400000.00000-aaattttt..c. html.
Nived Rajaraman, Yanjun Han, Lin Yang, Jingbo Liu, Jiantao Jiao, and Kannan Ramchandran. On the value of interaction and function approximation in imita- tion learning. In Advances in Neural Information Processing Systems (NeurIPS), 2021. URL https://proceedingg. wwwpeeeddiinnnnnnnineeeeeeeeeeee www.nips.ccpppprr.ffe........... wwtppcpepeapiieeeeeeeee caaeerrfllleppppppe ttteee//ppee//22///aaa /2a/s/hh// 0oacc11722115711ff21111111133333 Abt.rstctt.-atttt.ta.aa html. html..
12

---

Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster. Computational stanutaationll-staiitiiaall tradeoffs at the next-token prediction barrier: Autoregressive and im- itation learning under misspecification (extended abstract). In Conference on Learning Theory (COLTT, 2025. URL. wtt.httts//ppoceeeiieeee
mlr. www...mww.........e...e...m.eeee wrreess/v21/rrohateee
.ttml.
S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Intermational Conference on Artificial Intelligence and Statistics (AISTATS), 2011. URL https: ptttpp:://proceedingg mlr pawess/vv5/reea 1a. html.
Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. International Con- ference Artificial Intelligence and Statistics (AIS7A7S), 2010. URL URL.https:/pprceedinng
mlr. www.s//essvveee ross10a. html.
Lior Shani, Tom Zahavy, and Shie Mannor, Online apprenticeship learning. In AAAI Conference, 2022. URL sattps://ojs. aaaii org/index, http:////Aaaatttteeeeereee/e///e
Max Simchowitz, Daniel Pfrommer, and Ali Jadbabaic. The title of the paper. In Proceedings of Thirty Eighth Conference on Learning Theory, 2025. URL ht0o/ssimchoiit255a html.
mlr, presa//
Gokul Swamy, Sanjiban Choudhury, J Andrew Bagnell, and Steven Wu. Of moments and matching: A game-theoretic framework for closing the imitation gap. In International Conference on Machine Learning (ICML). 2021. URL https: http::///rroeee/ http://poooeeee.eeeee/ mlr. press/v133 /es//wwamm1le html.
Gokul Swamy, Nived Rajaraman, Matt Peng, Sanjiban Choudhury, J Bagnell, Steven Z Wu, Jiantao Jiao, and Kannan Ramchandran. Minimax optimal online imitation learn- ing via replay estimation. In Advances in Neural Information Processing Systems (NeurIPS), 2022. URL https: p/poceedinns wwwp:iiinnnnnnnnis........ nwwrips.. saapper_fieespppppeeee html.
Abstract- Confeet-ooooefeeccoooo erence -tt.:/aaccbbeee---battt-t-----oo
Umar Syed and Robert E. Schapire. A game-theoretic approach to apprenticeship learning. In Advances in Neural Information Processing Systems, 2007. URL https: https://papers. nips. Abstract.
html.
Volodymyr Tkachuk, Gellért Weisz, and Csaba Szepesvari. Trajectory data suffices for statistically efficient learning in offline RL with linear q- rerrealizability and concentrability. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// openreview wwt.:swweeeeeeeeeeeeeeeeeeeeeeee wew.//oromm.d-TuuuSStbta
Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez- Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: A standard interface for rl environments, 2025. URL https: //axxiv./ wwwp/a/////0..o...////// 17032.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018.
Luca Viano, Angeliki Kamoutsi, Gergely Neu, Igor Krawezuk, and Volkan Cevher. Prox- imal point imitation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2022. URL https://proceeddings neurips.co.m cc/ wttppppcccppppp.pppppppeppp wtw.:/sssicccco---ttttttee---oo Aww.-satttt---eee Conferenceceeeeeeeeeee erence. html.
Luca Viano, Stratis Skoulakis, and Volkan Cevher. Imitation learning discounted linear MDPs without exploration assumptions. In International Conference on Machine Learning (ICML), 2024.
URL URRLittts///ppeerevvie http://ooooooo/m/dd/adaa111
Gellért Weisz, András György, and Csaba Szepesvári. Online rl in linearly qd rrealizable mdps is as easy as in linear mdps if you learn what to ignore. In Advances in Neural Information Processing Systems, 2023, URL https: https:/
neurips cc/paper files/llapppppee paper/ h20p:///a/////a11133377777777660
html.
Tian Xu, Ziniu Li, Yang Yu, and Zhi-Quan Luo. Provably efficient adversarial imitation learning with unknown transitions. In Conference on Uncertainty in Artificial Intelligence (UAI), 2023, URL mlr. www...rrees/v.1////e x22////22..x html.
13

---

Contents of Appendix
Additional related works
15
B Omitted proofs
17
B.1 Proof of Lemma (performance difference lemma)
17
B.2 Proof of Lemma (regret of the policy player)
17
B.3 General concentration argument
18
B.4 Proof of Lemma (concentration linear case)
20
B.5 Proof of Theorem (sample complexity guarantee for linear Q realizable MDPs)
22
B.6 Proof of Lemma (concentration general case)
22
B.7 Proof of Theorem 2 (sample complexity guarantee for Q" reariiaizable MDPs)
24
B.8 Improvement for convex Q classes
25
B.9 Different sample complexity guarantee for finite Q classes
28
Technical tools
32
On the guarantees of misspecified BC in linear Qr-realizable MDPs
33
Additional experiments
34
E.1 with a simple expert class can outperform SPOIL
34
E.2 Comparison with IQ-Learn in the linear case
34
E.3 Omitted experimental details
34
14

---

A Additional related works
Classical analyses by Ross and Bagnell (2010); Ross et al. (2011) on behavioural cloning (BC) established an error propagation framework relating the suboptimality of the learned policy to the worst-case generalization eπror incurred in predicting the expert policy. They proved that this suboptimality gap upper-bounded by the generalization error up to multiplicative factor H² (where H is the horizon), a factor that is unavoidable when using the 0-1 loss for supervised learning. However, these results do not quantify the expert sample complexity, or the number of samples required to make the generalization error small.
recent line of work has begun to investigate the expert sample complexity assuming knowledge of a policy class 11f that realizes (or nearly realizes) the expert policy. For instance, Rajaraman el al. (2021) assume that the expert is deterministic and belongs to the class of deterministic linear policies Ii (defined in the caption of Table I). They prove bound on the required number of expert samples of order (HF2d) /e), where d is the feature dimension in the definition of det. Their technique is a reduction to the problem of multiclass classification in supervised learning, but their result not informative for settings with general stochastic expert policies.
Further contributions to understanding the sample complexity of IL under policy class assumptions were made by Foster et al. (2024). Specifically, assuming the expert is included within a known class, TE E IIo, they showed that one can learn an E-optimal policy (as defined in Equation (2)) after (
observing O (H2 log ITT))) /e) samples for deterministic expert or O( log [TT*) )/e) samples for a stochastic one (we report the dense reward case for brevity, though their bounds improve for sparse rewards). Addressing scenarios where the expert policy might only be almost well-specified, Rohatgi et al. (2025) demonstrate that there exists a computationally efficient algorithm that outputs an s-optimal policy up an additional approximation error of H log(W) min Di (IPT PTTE.. In this context, pSt is the trajectory distribution induced by æ, W is density ratio defined as
T (a] (z) (EE Th [a
W max TElL
max
max
It is worth noting that these guarantees become vacuous when the policy class I1 is such that at least one policy in ITe fails to provide sufficient coverage for the expert's 's actions (leading to W 4000 as TT. (a æ) gets close to zero for relevant state-action pairs and timestep where TT, xx) >> 0), or if the minimum Hellinger distance minzen" (HP (PTe) is large. Alternativel,, Foster et al. (2024) proved a misspecification result where the additional error is min X 2FF P*t). This misspecification error is measured by the x² divergence, with a leading coefficient constant in H and W. However, the x" divergence an upper bound on the Hellinger distance that often way too loose to be practical. In similar vein, Espinosa Dice et al. (2025) proved benefit in terms of error propagation for a local search algorithm over behavioural cloning in misspecified settings, under the assumption that the learned policy is allowed to reset to states visited in the expert dataset.
Our work aligns with the recent renewed interest in proving refined expert sample complexity guarantees for offline imitation learning but distinguishes itself by swapping out the expert realizability assumption with a structural assumption on the environment. Early explorations for similar settings can be found in classical works by Abbeel and Ng (2004) and Syed and Schapire (2007). These studies proposed offline learning algorithms for MDPs with reward functions linear in a collection of features known to the learner, under the assumption that transition dynamics of the environment is also known. Versions of their approaches that do not assume such knowledge typically incur a worse sample complexity and often apply only in the tabular setting. Our work generalizes these classical approaches by removing the need for known transitions and for rewards to be linear in the features, as well as going beyond tabular MDPs. Notably, the linear Q (T-realizability assumption can hold even if the reward function and the transition dynamics are nonlinear. We summarize our comparison with these and other related works in Table 1.
Our work focuses on learning a Q-value from expert data and, in this regard, is closely related the practical work of Garg et al. (2021). The novel regret decomposition employed in our analysis of SPOIL demonstrates, we believe for the first time, that provable guarantees are achievable by directly learning an action-value function from expert data. This contrasts with the majority of theoretical and practical imitation learning approaches, which typically first use the expert data to learn a reward function and subsequently use this learned reward function to infer an action-value function.
15

---

As we mentioned. SPOIL is very related to AdVIL. However, a key difference lies in the analysis: Swamy al. (2021) conduct an error propagation analysis for AdVIL. From this, they conclude that AdVIL is equivalent to BC in the sense that if the loss for either method is at most e in every state, then the suboptimality of the extracted policy in an episodic setting with horizon H is of order H for both. However, this type of result does not investigate the assumptions or the number of samples needed to ensure these losses are indeed less than E. Our work addresses this open question, establishing a clear distinction between the sample complexities of SPOIL and BC. Specifically, SPOIL and BC (and their respective analyses) rely on largely orthogonal sets assumptions, making the two approaches complementary each other: expect SPOIL to be more suitable for imitation tasks with complex experts but simpler environments, while BC may be the preferred choice when this situation is reversed. Our sample complexity analysis for SPOIL critically relies on the Q-player using a best response strategy, and it is unlikely that equivalent results could be achieved using a standard gradient ascent step for the Q-player instead.
Very recently, Simchowitz et (2025) analyzed the error propagation properties of offline imitation learning algorithms in continuous action MDPs, showing that an exponential dependence the horizon the problem unavoidable if no structure is imposed on the environment. On the other hand, the same authors point out that if the state-action value functions were Lipschitz in the action space, then efficient learning would be possible. Conceptually, we believe that the SPOIL algorithm could also be applied in the continuous action case. Such extension would suggest that another scenario enabling effective imitation learning in continuous action spaces arises when the learner has access to suitably expressive class of state-action value functions.
Following similar line of research that studies imitation learning from a control- perspective, Block et al. (2023) studied guarantees for generative behavioural cloning, assuming access to stabilizing policy dubbed a synthesis oracle. These policies can be computed exactly if the dynamics are known, assumption which is not imposed in our work. However, when provided with such an oracle, Block et al. (2023) derive bounds on a stricter metric for imitation. Specifically, they bound the probability that expert and learner trajectories diverge at some time step, as opposed to the difference in cumulative return that we analyze in our work.
16

---

B Omitted proofs
In this appendix, we provide the omitted proofs of the main results.
B.1 Proof of Lemma (performance difference lemma)
We start presenting the performance difference lemma proven in more general form which allows one policy to be nonstationary.
Lemma 1, Let it be a stationary policy and n' be any policy. Then,
p" E (Q (0
(X)]
Proof. Consider the Bellman equations for the stationary policy æ. For any state-action pair (s, a). we have
Q" = r(x, a) + P(x'l ax)"
N'EX
Averaging both sides with the distribution 10² and reordering the terms, we obtain
Σ 5 (2, Entle, Q" (²((za))=+ -7 (000)((())))))
E P(z' za))
x'ex
Σ Vo()) Σn (2, (1. (z)x))
where we used the flow condition of the occupancy measure nt the last step (see Equation 1). The claim then follows by noticing that p" (1 - 7) Ex (*) and px Exa ftt (x, a)r(s, a).
B.2 Proof of Lemma (regret the policy player)
Next, we apply Lemma 14 to the special case of the exponential weights update, where the divergence chosen to be the KL. divergence, and use it to derive bound on the regret of the policy player.
Lemma 2. For any and any state-action pair (z, a). consider the sequence of policies starting with a as the uniform policy and updated as Th41 x) x (a ()) for some function
Qu: X x A + R such that \Qulloo I T- Then, E [(TH: Qx) I
log A
nk
201 2(1-))
Proof. Let us recall that
[(TR. Qx) ((x,A)~uurE (x A) - Qx(X,
where n.. is potentially nonstationary policy. To continue, let consider the stationary policy
Th X' >> A (AA) that induces the same state-action occupancy measure the expert, i.e., such that
TE = R This equality can be guaranteed by choosing, for any (æ,a) E X x A, 7, (a]=)
(2,0)) if (xx))) # and (a)a) otherwise, where my (AA) is an arbitrary distribution. Then,
(x)
continue as follows
C(TTE, Qu) = B( Qx A) Qx(X,Ta)
E(x,A)mmpn Qu (x(X.
Σ AE (x)
Qu(2, x)) (a(a/x))
aEA
Summing over & E [K], we obtain
C(TT, Qu) Enm (x)
Σ (u(c)a)((((ll=) x))))))).

---

It remains to prove the following bound.
K Σ
log A
11K
E 1= AE
2(1 - 7)²
The result is proven as a particular case of Lemma 14. Specifically, we have that when V is the A 4-dimensional simplex and the Bregman divergence is the KL divergence, it holds that
Ihe @ exp(-17(k) arg min (Cx, v) + D(, vEV
2k+1
(1, exp(-nfxx)
where ④ is the elementwise product. We apply Lemma 14 for each state E X, replacing Tk = [- 1)) and & = (2((2,) We obtain that for the update Th+1(a x)) x T&k (a (r)e the guarantee in Lemma 14 holds. Moreover, in this setting we have
1, and lmax 1-7"
Given that for any state-action pair (I,a), the initial policy is mi (a x)) ((T(+12)) (1 x)) s log Thus, we have the following bound
1 we have that
A
log A
n
(ull (a <
7
2(1 - >)²
acA
and the conclusion follows from AH being a probability distribution.
B.3 General concentration argument
To prove the main results this paper, we prove a general concentration inequality that we will use for the iterates produced by both Algorithm 1 and Algorithm 2. Specifically, when analyzing Algorithm 1, we consider the policy class Thm defined as follows
expl (1 (4((,, (x)
Hinn
π A(A) 3(0x) C ((BB).x(al+ ΣBEA exp EE (50(z, b), b),0x)
(3)
while the nonlinear case (Algorithm 2), we will consider the policy class
exp E Qx(2,a)
Te x ((A())) 3(QK) T(ar(()))
(4)
EvEA exp
11 E Qu
The result is the following.
Lemma 5. Let Q R.X be a value function class such that for any E Q 11 S +
ke= for a policy sequence (Tk) ) belonging to a policy class IT. For any l E [K], recall that for any policy x. and function Q, the objective function is defined
Consider the sequences of estimated objective functions {[(mes -) ))KK
[(T: Q) = E (xx,))) (Q(X,A) - Q(X,
Then, with probability larger than 1 8, it holds that for all k E [K] simultaneously that
8 llog 2N. (Q x II, |1- 1111o,)) 15
4e
A(T)) sup
[(TE, Q) L(TTE, 2) < inf ex50
QEO
1-
(1 - 7)² 2
where, for any (Q, (Q,T),
(T) (Q' n') E Q 11, we defined the distance ((Q,T) (Q', x2',a')lla x')oo..11 =
1|Q Q'1l= + max [| r) - x' x-(1x)]11
Proof. Let us recall that for any Q E Q and any ls E [K), we have
1(TR, Q)
1 a
Q(x A1
Σ ma (x(alx))((xxaa)
Tr
18

---

and notice that C(TT Q) is not an unbiased estimator of [(TK, Q) since the policy gy depends on the expert data. Therefore, we aim establishing a uniform concentration bound over the policy class II. To this end, let us consider a fixed pair (Q, .T) E C x 11, |l-| 20,)),)) and notice that [(T, Q) is an average of random variables of the form
W (Xx
Σ aEA
x x (x)
where E [Tg]- Each W; is an unbiased estimator [(T, Q) since x is fixed (i.e., not a random
quantity depending on the expert data) and (Xg, Ag) j for all i [Te]. Thus, for any i [T]] B[W;] = (m,, Q). Moreover, notice that for all E [Ta]. - - S W; S T-y- Therefore, by an application of Hoeffding's inequality (see Lemma 13), we have that for
PTa(1 - 7)
-)) p C| Q) [(T, 23 20 S 2ex
That is, choosing t (2/8(2 (1-7)*m
guarantees that with probability at least - 8,
8 8log(2/8)
C( Q) [(T, (((,,)) $
(1 (1-7)
Applying union bound, further have that with probability least 1 6, for all (Q, (x x I1, 11) it holds that
8 llog 2N
II, 11llo.)))))) 2
[(T,, Q) [(T, 21 $
Recall that (2 11, 1l is assumed to be an e-covering set the space Il with respect to the distanec I1- For any pair (Q, mx) E @ II, let (Qes TR,e) (2 x II, I1-lo,.,)) denote the element of the covering such that [|(Q, mx) (Qc, Tk.c) I c. Then, we have that
TE Q( 4)) (x(
L(TA Q) L(mkeer ad)
TB
n
(a Xx) ( (x(4(xx))((xx
+
TB
i= aEA
< 11Q Qelloo +
Tk.e (a.e -
TF
aEA
(a) x;) (Q(X), -Qe -
+
TB im 1 acA
Noting that for any Q Q. inequality, we further have
|1Q1
L and that for any state x, mT(. (x) E ((A), using Hölder's S i
S 11Q - Qella max [|TAe((- TT x)]1 I|Q Qe
[(TT) Q) A( Qc)
2 211(Q, T.) - (Qrs TM. lllc.
1
26
1 ?
19

---

where we used the definition of (Tk,es Qc) and y E (0, 1) in the last inequality. Similarly, for the true objective we have that
[TT,, Q) L( 2c)1 - R (x) [Q A) - 4)]]
+ Ex [Q mk) - Qe(X, Tx,e)]
I1Q Qelloc + 1x [Q(X,, TR) Q(X, TR.,)]
+ -x (Q kk,e) - Qe Tk,,e]]
- 11Q - Qelloo + maXxex Th. (x)=)) TT [x]]|
+ 1Q Qellxo
1-7
2E
1-7
Therefore, with probability at least holds that for any [K] and any Q Q.
[T Q) [( 2) < [(TR. Q) - [(THHe. 2.) + [(TR.e: Qc) L(TTkee Qc)
+ [[TK, Q) - [(TK.e. Qc)1
log 2N
Q x 11, 18)
4e
V
(1 (1-7)<r TE
Moreover, since the above bound holds for all Q Q, it holds for the supremum over this class. With probability least 1 ō, we have for any & E [K] that
8 8log 2No Q x II, 11110,,1)) 11llo,)))))) /5)
4c
L(TK. Q)
[(TT 2)
sup QEQ
+
1-7
(1 >)
The proof is concluded by noting that the above proof holds for any covering size 0.
B.4 Proof of Lemma 3 (concentration linear case)
We now instantiate Lemma 5 in the linear Q setting. For this purpose, we compute bound on the covering number of the class Iin. defined in Equation (3).
Lemma 6 (Covering number of Thin). For e >> O, holds that the e-covering number of the policy class Tin can be bounded as
NT 11-111) (1+ 2KnBoBBA
where, with a slight abuse of notation, ||-I|, denotes the distance defined for any n, n/ E Iin as || T'll = supxex [| x) x'(- >'(-12)ll Moreover, let
Qin = {Q: x A + R 30 E B Bo). V(x, a) E E x A, Q(x, a) (00,6(0000 a))}
be the class of linear action-value functions. Then, holds that
4K 4Kn 2d
No NV(Qun Qum x Iin 1H11o..)) < (1+
Proof. Let us consider two policies स and in the class I[n. There exist 01...., 0x E B(BB) and 8....., ,''x B B(B)) such that for any sate-action pair (I,, a) X A, and x' can be written
exp(n p(x,, a), ΣK 0z)
ata x² ELEA exp 17 ((xx, b). Σk= 0z)
and
exp exp(1 (pp(n(p(x,0)) Σk 0%)) EoEA exp (f(,,) b), Σx= 0%)
7'(a 1))
20

---

In particular, let us fix state E X, and denote 0x = E k= Ok 8xx = =E 8%. First, by Cauchy-Schwarz inequality, have
S [+ - x'( (-1x))
By 1-Lipschitzness the softmax function (Lemma 15), holds that
[T[-|2) - x1112))11 - ny [lll,,, ), 0K -8x)1
Σ
(1((1, a), 0K 0kk))²
"V
aEA
17
Σ
11,( a)l 110x xx
(Cauchy-Schwwel
aEA
< nB 0x xxx
where the last inequality follows from the bound the features yp in Assumption 1. Notice that 0x, 0'x E B(K Bo). Therefore, the e-covering number for Ihi with respect to the distance ||-I| Nr. (ITim ). upper-bounded by the 7B.4 covering number of the Euclidean ball 2 B(K Bg) with
respect to the distance ||-1|, and
Ne 11-111) S N (B(K 11-11)
Bo
where we used Lemma 16 in the last inequality. For the second part of the lemma, let us consider Q,Q' E Qin. By definition of Qin. there exists 0, E B(BB) such that for any state-action pair (2) (( (p(z, a), 0) and (x a) = (1(2 a), 0*). Then,
max 1Q(x,a) - (x(x,))== X
max 2.EEX'A
1(0(2, a), B 0'l
B
Therefore, the 6-covering number of Qiin Ne(Ciin Il. ). upper-bounded by the c/ coverrin number of the d-dimensional ball with radius Bo, N. B, (23 ( BB), 11-11)- We have
(Q NB.,, S [1 BBaBB d
c
Finally, the proof concluded by noting that
N.. Qiin 1m (1-1lo..)) s Ne//(1llm (1-111) l1
Finally, the following result proves the concentration of the estimators used in Algorithm 1. Lemma 3. Let { (TkkkE be the sequence of policies generated by Algorithm and let A (Tt) be defined as Proposition Then, with probability least 8, it holds that for all k E [K]
2 + 32K Bn
( S K
+ +4/ (1
log
7)²² T
(1 (1-7)
21

---

Proof. By Lemma 5, it holds that for all & E [K]
8 log
2N, Qtin x Min, 11-1
4c
( v inf c:>0
--9
(1 (1-10 -)-
2 log 2N(11>)//KK Qtin Min: 11-1loo,)
1 S K
+ 2
7)²
2d
1 $
2
2
+ 2
log
1+
K
(1 7) TB
1-7
1
d
(2 3/ B.p.A
$ + 4
log
K
(1 7) Te
(1-
where the third inequality follows from Lemma 6.
B.5 Proof of Theorem 1 (sample complexity guarantee for linear re-realizable MDPs)
Theorem 1. Let Assumption 1 hold. Run Algorithm for K
2 log A
iterations, with learning
(1 (5-
rate (1-7) 2og A/K, and O
[1->)" log Be
d
samples collected by any
(1-7)c
expert policy Tg. Then, the output satisfies 1T p= = =(E).
Proof. By Proposition have
K Qk)
2 K K [[A(T+)]
E
p
B[C(TRK
Σ
K
A=1
Using Lemma with a learning rate of v = (1 (1-)) v)
2log and dividing by K, we obtain that
K ((TAiQu) S 1 (1 (1-
2
K
Therefore, setting K
(2= guarantees
2 20gg A
& EE C(Tss Qx) S E. Then, using the high-
probability bound in Lemma 3 and the fact that 1 I A(Tx) random variable bounded by 2(1 ---)-= almost surely, we obtain the following expectation bound which holds for all > 0,
d log B Ba
25
[(((T)
+ +C
+ 1-7
K
K
(1
(1 7)68
for some C E IR. Note that the choice of parameters ensures K < 5. Setting 8 s(1-)) and
To 2 2Cdd
Bo (1 2)22 (1 1)=
log
this bound implies that 2 ΣE k=1 ({)) < 4s. Thus, we conclude that E. [pDe p= < 5c. K
B.6 Proof of Lemma 4 (concentration general case)
Before presenting the proof of Theorem 2, we provide a bound on covering number of the class Q x HI, where Hg is defined in Equation (4). It turns out that the covering number of this class exponential in K. In the linear case, the exponential dependence in K was avoided because the state-action value class is closed under addition.
22

---

Lemma 7 (Covering number of Il)), For E > 0, it holds that the e-covering number of the policy class Hg can be bounded as
MT (TI1:1I.11)) S win (2,11-11))
where, with slight abuse of notation, |1-112 denotes the distance defined for any n. E ll as || n r'111 = suPxex (- x) - -x((-1)) Moreover,
No o x ee I| llel....) SN ZRNd
(2, 111100))) K+1
Proof. Let us consider two policies т and x' in the class Hl. There exist Q....., QK E Q and o Oxx Q such that for any state-action pair (I, a) E &' x A, a and n' can be written as
exp (1 E Qx(2r
Tia x)= ENEA exp 11 n Qx(x; b)
and
exp 1) - Pi a)) <'aa| x.)
k EDEA exp 17 " 22 (zx b)
Let æ E X. Using |1-111 $ v ||-|| in RA and by I-Lipschitzness of the softmax function (Lemma 15), it holds that
[ 7 (r)(11=)]11
A | x)) +1(+=>)
SIVA
Σ (Q)(z,-) ((,,,)))(((()))))
S nvAA
Σ -2((,,))
(Triangle inequality)
k=1
nA
Σ A=
sup QQ a) (x(xxa))
(I S vA 11
aEA
K
S 7A sup
Σ
sup Q2(2 a) (h(2,a))
=
aEA
K
< n
11Qx 1a1lo
(Triangle inequality).
A==1
In particular, this implies
K Qxl
(-112) (+1x)]] S 74 Σ 11
max TEX
Thus, the e-covering number for IT. (T e |1-11 is upper-bounded by the K coveriig number of the class Q to the power K, i.e., N kiz (Q, II K Thus,
Ne I1-II)) s N KGa (2,
The proof is concluded by noting that the covering number increases with the precision (when decreases), and therefore, we can write
No. @ x Ho. (Hlb,,)))
(1-11)
s (N W. 2kna (2, 1 (2.11-11
S
K+1
23

---

Finally, the following result proves the concentration of the estimators used in Algorithm 2.
Lemma 4. Let Q C XxA denote an arbitrary class, { k=1 denote the ueeaate produced by Algorithm and let ((Ts) ) be defined as in Proposition Then, with probability at least holds that for all k [K]
8(K 1) log 2N 1-> (Q, (0.11-122/66)
1 A(T)) S K
SK
+
(1-7)
Proof. Note that by construction, the policy sequence { kE(KK] generated by Algorithm 2 belongs to the policy class Ile. Therefore, invoking Lemma 5, we have that with probability at least 1 6, for any [K]. holds that
log 2N,, (Q x To, Nee.11-1.. 11 18)
4 - 7
(TT) S inf
+
(1 - 7)²
Therefore, choosing 4K
we get
8log 2N
2 x IT 11-1100.,)
A A(TA) S
+
K
(1 71-7)²Tm
8(K + 1) log
2N 1-
(Q, 12-11:110)/6
8K2nA
K
(1 - 7)
where the last inequality follows from Lemma 7.
B.7 Proof of Theorem 2 (sample complexity guarantee for re-realize MDPs)
We are now ready for the proof of Theorem 2, which we restate for convenience.
Theorem 2. Let Assumption 2 hold. Run Algorithum for K
21og
iterations, with a learning
(1-
rate (1 / log A/K and ( log expert Te, where e' (8v2K3 3/2 log A) Then, the output satisfies LE [p p=-01] O(s).
(1-7)'=7
log
(v.(())1)))))) samples collected by any
e(l->)
Proof. Recall that by Proposition 1, we have
K
K
E
E|C(TR:
Qx)++ + ([)()
K
K k=1
k=1
Then, by Lemma 2, holds that
K
log(A) B[C(TA Qa) <
Σ
+
K
nk
(1 ?
k=1
Moreover, by Lemma 4, with probability at least 5, it holds that
8(K - 1) log
2N 1- (Q, 1.11ee/)))
SK* nd
( S
(1 11-7) -->))²=
Since K Ek= A ( is bounded almost surely by 2(1 7) we have that for any >
1 K
8(K + log
2N 1-x aK4nd
(2, 11.1,0///
25
(T)TT < K
+ +1
K
(1 7
1-
k=
24

---

Setting = (1 7) log A)/K, K, we get
E pa
2 2log( A)
2 K
8(K + 1) log (2N22 (2,111100)/ 11.1)))))/))
45
V (1 - 7)²
+
+ 2
+
(1 11-7) >)
1-7²
where we denoted e' 3/2K3/2 log(Ajd
Setting 6 مامم and K
log a and noting that (1-7)'
K S & (for < L [0, 1] and A 2 2), further have
log(A) log
No, 11-1100)
IR p m
p= Se+e+C
(1 ETT
(1 71-
for some constant 0. Finally, setting
C2 log((A)
(2,
TB
7)
log
(1 71-77e
where e' a3 32(1og A
after plugging the value K, we guarantce that
IE p dE
x=) ous
O(e).
B.8 Improvement for convex Q classes
In this section, we show that, when the class of state-action value functions Q is convex, we can improve the sample complexity from Theorem be of the same order as in the linear case, i.e., O(e-2) instead of Oge-A).
Assumption (Convexity of Q). The class of state-action value functions Q is convex.
The key observation is that, when Q is convex, the covering number of the induced policy class TTg can be bounded without an exponential dependence in K, as we show in the following result.
Lemma 8 (Covering number of Il)). Let Assumption 3 hold. Then, for e >> O, the e-covering number of the policy class Ho can be bounded as
Nc 11-111) S 1.,N5x00,1111..
where, with slight abuse of notation, denoted II-Il, the distance defined for any n, a' E Il a - T' T'll1 = supaex [] x) x'(- x'(11=)l1, Moreover,
N. ( To To, (+llo..)) $2.
.i.....QA. QK E and Qi.... Q'k E Q such that for any state-action pair (I, a) E X' x A, क and n' can be written as exp (1IK (x(2)))))
Proof. Let us consider two policies and x' in the class II There exist Q.....,
(a r) EsEA exp | (x(x;b))
and
exp 1 kK (2(2;
<' x)) ΣBEA exp 17 Σ (x(
Let e X. Using |1-11, S VA ||+|| a and by I-Lipschitzness of the softmax function (Lemma 15).
it holds that
|m(112) n' r1(11=))1 VA || - <-(1=))]
K
v A
(Q - -(((t,)))(((,,)))
K K-1 Σ Qu(x,)) - KK-K Σ
K
< SVAK
Q (z,
Jom
km
25

---

At this point, we can define ((2, - K-1 Ek= Qx(a,a) and ('(x,a) = K " (x
for all z, a E X' A and obtain
[- --
S AAKK ([Q ('xx)))l
$ nAK [Q( - (z,-))
(IHI o.
< nAK Q1Q 2'1lxo
At this point, notice that by convexity of Q we have that Q E Q. Thus, we have, the e-covering number for llg, Ne (1lo, Il-Il,), is upper-bounded by the Kyd -covering number of the class Q, i.e.,
N Rin (2, 11 Thus,
N. 11-11)) SV Kia
(HI))
The proof is concluded by noting that the covering number increases with the precision (when decreases), and therefore, we can write
No. Q He 1H
SN l1-11)
1u (2, (
S N V (0.11-1..)
Importantly, the covering number of IIg is longer exponential in K if the class Q is convex. Therefore, plugging Lemma 8 into the general concentration argument in Lemma 5, we obtain the following result.
Lemma 9. Let Assumption 3 hold, let { be the sequence of policies generated by Algorithm 2, and A (mxx) be defined as in Proposition 1. Then, with probability at least 6, for any [K]. holds that
16
2N 1-7 (Q. 11111-1) 1K294
((T
S
+ K
(1 (1-7)²T
Proof. Invoking Lemma 5, have that with probability least 5, for any ls E [K], holds that
8 8log 2N,. Q x IT, 10-11110,,)111
4e
((Tx) S inf
+
<
--7 7
(1 - (1-7)2m. 7)
Then, choosing e
1-2 T get
8 llog 2N W//KK
@ 1l 11:1)
A(TA) S
(1 73
16 log
2N 1K244
(2, 11:10
7--7)a ? TT
Finally, putting all together we can derive the following sample complexity bound for the convex case.
Theorem 3. Let Assumption 3 hold, and let out be the policy obtained running Algorithm 2 for
K = 2log A. iterations, with a learning rate 1) = (1 - -) log( A)/K and
T =
(2. )
22 log
21-
s(1-~)
26

---

(1-7)²6² 32(log A)" Then, the oulput satisfies
samples collected by any expert wa where e'
p p (())-
Proof. Following the arguments used in the general case, and setting 1) = (1- - 7) v log A)/ K, we get
E pT pr
2 (o)
+
16 16log(2Ng 11)))))//))
+ 1-7¹
46
(1 2)²K
K
(1 -
where we denoted
Then, setting 0 = [1~2le and K =
2 2log (1-7)'E7 we further
8/2K3/2 /100////ol(/))) (log(A)4
have
16 (2.111))) 7)8))
E T
Se+
+
(1 71-
Finally, setting
64
(2, 11-11=)))
TB 2
log
(1 2²2
a(1 -
we guarantee that
TE
p pun
= -(E).
This result also provides proof for a different sample complexity guarantee in the general case, as we show below.
Corollary 1 (Convex-hull reduction). Let Assumption 2 hold and let out be the policy obtained running Algorithm for K 2 and
iterations, with a learning rate 17 (1 -- ((1o))))
(1-7)"²²
(convv (111o)))
To = o
E222 log
<(1 (117))
samples collected by any expert where e'= = a1-
32(1og A)2 and conv(.) refers to taking the convex
hull. Then, the output satisfies IE pT -pmh-p0m
O()..
We note that, in general. there is no way upper bound the covering number of conv Q) in terms of that of Q; the former can be much larger than the latter. Therefore, the sample complexity in Corollary I can be strictly worse than that in Theorem 2, depending on the structure of Q.
Remark 1.
Proof. We follow the same steps as the proof of Theorem 3; the only difference is that we replace the convexity assumption on Q by working with its convex hull in the covering-number bounds.
Fix any policy æ and recall that [(T;; Q) is linear in Q. Since a linear functional achieves the same supremum over a set and over its convex hull, we have
[( Q) sup [(T; Q).
sup QEcouv( Q)
QEo
(Note the same argument holds for the population loss [(T; Q).) In particular, the critic update in Algorithm/ 2 (which selects Qk arg max [(m=; Q)) is consistent with optimizing over conv(Q): it already chooses an element of conv( Q) (since Q C conv(Q)) achieving the same maximum value.
We check that the boundedness is preserved after taking the convex hull. By Assumption 2, we have |IQ1| < (1 - - for all Q E Q. Hence for any Q E conv(Q) written as Q Σ, n2 with some discrete probability distribution w and Q(+) E Q, we have o E n. | S -
Thus the boundedness condition used the concentration arguments continues to hold when working with conv(())
27

---

Next, we show that the covering number bound of Lemma 8 continues to hold with Q replaced by conv(Q) Q) on the right-hand side, even if itself is not convex. That is, for all > 0,
e I1-l1) S (c/ (Q), l1+11oo)
(5)
Indeed, take any n' E H. By definition, there exist QI...., that, for all (I,a) E X A,
........KK QK E Q and Qi...., Qk E Q @uchh
Taa 2) exp 1) E
k QM(1,a))
exp 1) Ek=1 (11,a)
a' x)
ΣBEA exp Ek= Qx (x(
ΣBEA exp
E k= (1()
Repeating the Lipschitz argument in Lemma 8, we obtain for every I E X, ||<(-|2) n' r1)11=)]1 S /|
where Q= Q >
k= Qx and Q' = K-K Em= Qz Crucially, even if Q is not convex, we have Q, E conv( Q). This proves (5) exactly as in Lemma 8. Moreover, since Q S conv( (Q). we also have (2, 11 S (c(onv(()) (1-1.1-1l.o).. Combining with (5), we obtain for all 0,
No. (e(xxx ee: Il-Ila..))
S [ (Q), 11-11==)
The rest of the proof is unchanged, and yields the stated condition on тæ with Ngr (conv(()))) (1 in place of Ner (2, (o.))
B.9 Different sample complexity guarantee for finite Q classes
In this section, we provide an alternative sample complexity guarantee for Algorithm 2 in the special case where the value-function class finite. The key observation is that when Q is finite, the set of policies that can be produced by Algorithm 2 up to iteration K is also finite and can be controlled by simple counting argument. This allows us avoid the govering-numbly bound of Lemma and obtain a dependence in Tr of order Ō (up to logarithmic factors), albeit at the cost of worst dependency in the size of the class 2, which we discuss later. We start with two standard combinatorial lemmas, that we prove here for completeness.
Lemma 10 (Stars and bars). Let m 2 and 2 0 be integers. The number of integer-valued vectors
n (M1,.... mm) E Nm such that 5m n2
= t is
KNENT E NM Eド= n = =1}|
t + m -1 1)
m
Proof. Consider the set St, of strings of length ( m - over the alphabet {+, |} containing exactly t symbols * and exactly m symbols |. Clearly, |S,.ml = ( (t+---1) since specifying such a string
is equivalent to choosing the (m - 1) positions of the bars among + m - 1 positions.
We construct bijection between St,m and the Ne.m = {n Nm Σド= 71 = -.. Given string E St St.m read it from left to right and let ns) be the number of symbols occurring between the (j - 1)-th bar and the j-th bar, with the convention that the 0-th bar is placed before the first character
and the m-th bar is placed after the last character. This produces vector
n(x) =
(s)) E N
By construction, the total number of stars in the string is t, hence ΣØ= n2((s) = so n(s) N
Conversely, given any n (Mi...., Rmm) N, define string s(n) Se by concatenating n stars, then a bar, then n2 stars, then a bar, and so on, ending with 7'm stars:
s(n)
12.2
This string has exactly t = Ej= ny stars and m - bars, so s(n) E St,m- Finally, it is clear from the constructions that n(((n)) for all E Nr.m and that s(n(s)) = s for all E Stm. Therefore - ns))) is bijection between St,m and Ne,ss and we conclude
(. m 1)
Wm.ml = |Smml
m -
28

---

Lemma 11 (Hockey-stick identity), Let m 2 1 and K 2 0 be integers. Then
m -- K + +mm m - 1 t=
K
m
Proof. We give short proof by induction K using Pascal's identity. For K = the left-hand side equals (w--) = 1 and the right-hand side equals (m) 1, so the identity holds.
Assume the identity holds for some K 2 0. Then
K+1
Σ m -
+ - 11)
m (-=-))
m
K + + m
)
+
m
By the induction hypothesis, the first sum equals (K+*)) Hence
K+1
Σ
1 m
m - - 1) =
K + m
K m
+
m
1
1=
Applying Pascal's 's identity
(+) + ((-1) = 1 with N = K + m and r = m, we obtain
(K
K
+ m
K + m
(K+
K + m + 1 1) (K + 1)
m
This is exactly the desired identity for + 1, completing the induction.
We also provide an upper bound on binomial coefficient that will be useful later.
Lemma (Binomial coefficient upper bounds). Let m 2 and 2 0 be integers. Then
K + m
c( K + m)
m
m
particular,
K +m)
e(K' + m)
log
< m mog
Proof. We start from the factorial expression
(K K + m (K + m)!
I1 (K + j) m!
m
K!m!
Since K +j S K + for all j [m], we have
m
II
(K + 5) m)
Next we lower bound m!. Using the integral bound
m
/ log x dæ = [x log x - x|""" m log m m + 1,
log 2
we obtain
log(m!) 2 m log m - m +
which implies
m! 2 m log mm
m
m
Combining this with (6) yields
K + m
(K + m)
ee + m)
<
(m/e)
m which proves the first inequality. Taking log both sides gives the second.
m
29

---

We are now ready to state and prove the main result of this section.
Theorem 4. Let Assumption 2 hold and assume that Q is finite with candinality m = |2| < oc and
A 2 3. Run Algorithm 2 for K
2log iterations, with learning rate = (07-)) 7) 2 2
(1-7)'E²
and = 0 (1-7) log log A (1-7)e)
samples collected by any expert Th. Then, the output satisfies
pm (E))
Remark 2. The result above combined with Theorem shows that, for finite Q, Algorithm 2 returns an (e)) (optimall policy with a number of expert trujectories scaling as
m
log (1- )
log A
m
TE =
min
(1 22 log
(1 (1- log
(1 (1-
This shows that Theorem meaningful only when m relatively small, because we are trading an exponentially worse dependence in m for better polynomial dependence in e-
Proof. We follow the same proof structure as the other theorems. By Proposition 1, we have
K
K
E
p
B[C(TK:
Qw)+
2
Σ
B[A(T))
K
K k=
Then, by Lemma 2, it holds that
1 K
Σ
[[[(T(:QU))
s log(A)
1
K
nk
2(1 7)²
Let Q - (Q ((m))
}.
For any vector ( Rem) E N and any state-action pair
(x,, a), define the policy n, by
exp 17 3= n (2,Q(55 at)
(n (+)
ΣiEA exp 11 12,
Define the (finite) policy set
Tn Pa:nER N Σ
S K
==1
Note that for any he E [K] Ta E TT Indeed, Algorithm computes policies the form
Th 1) exp 11 1 (z)
EvEA exp 1 Qi(2, b))
Since each Q; E Q, there exists a (random) count vector (k) E N such that (k) of indices E (1...., k 1} with Q; Q6i). Then E n 1 K and
n, equals the number
k-1 Σ Q1(1,a)= = Σ
n m0 (z,a) 1=1
which shows मe = (k) E IT Km Next, we bound [ By Lemma 10, for fixed integer 2 the number of vectors n E N satisfying E ny = t is
m-1 (++--1). Therefore, by Lemma 11,
K
+ m 1m-1) 1) =
1)
K m
m -
m
t=0
30

---

Fix π E K. and Q E Q. Recall that
(x A1 =
Q) 1 Σ
[(T; Q) = ( 4) Q(x,
Define the i.i.d. random variables
Zi Q(x A. Q (x( m).
By Assumption 2, 1Q 5 T-g' hence 12 S - By Hoeffding's inequality (Lemma 13), for
any <> 0,
(- [1
- 7)²
Q) - [(T;; Q) }
s 2exp
Let M km || < (x+)). A union bound over all pairs (T,, Q) E [T x Q yields that
with probability at least 8.
8 8log(2M/8)
sup sup [(TT Q) - [(T: [(T: S x QEQ
(1 7)²
Thus, on this event, for every Im we have
8log(2M/5) 1--7)²=-
A = sup [(T; Q) - L(T: 2) $
QEE
Since Th Im for all & E [K]. we conclude that on the same event, A ( is bounded by the same quantity for all & [K]. Furthermore, note that for any n. A(T) I T- almost surely. Therefore, for every k,
2
2 K K
(log(2
48
E E[
TK S 2/
(1 7)2
1 -
Finally, setting f) = - /)
2 log
we get
K
log A
8 8log(2M/8)
48
E
pm
p
+ +2
²)²K
(1 (1-7)²²,
By Lemma 12, log M I m (4K). Setting K
2 2log
and
(1-2) yields
(1 (1-7)=²2
E
0
yout
S 2 (1 21 TB
V
8m
log
64 64 A (1 (1-7) 323
t
remains to choose T. so that the remaining term is less than E, i.e.,
Cm log
log
Tv
2 (1
7){ (1-7)e)
for some constant > 0. With this choice, obtain E pT m0 O()), concluding the proof.
31

---

C
Technical tools
Lemma 13 (Hoeffding's inequality; Vershynin, 2018, Theorem 2.2.6). Let XI,...; Xn be indepen- dent random variables such that [X,] M for all i. Then, for any t > 0,
Σ (X - - 2=1
>
S 2e
2312
att
Lemma 14 (Simplified version of Orabona, 2023, Theorem 6.10). Let us consider a non-empty closed corvex set V, arbitrary sequence of adaptively chosen loss vectors (fx)k=1 such that ||&xlloo S Emaxs and let D: V int(V) - IR be a Bregman divergence induced by a X-strongly convex function in the nornrmm Then, for all V, the sequence (Ix) generated for any k as
Fk+1 arg min (lx, (((,
VEV
for arbitrary initial satisfies
(4a, u) D(,,
nKKe maxx
2X
Lemma 15 (Gao and Pavel, 2018, Proposition 4). For any 0, let the softmax function be defined for any E I as
softmax(2)
E== e
(E(n)
Then, the function is n-Lipschitz with respect to 11-112- That is, for any 2, R", we have
|softmax(2) softmax(2 II2 S 1) || z'
Lemma 16 (Covering number of a Euclidean ball; Vershynin, 2018, Corollary 4.2.11), For >> the e-covering number of the Euclidean ball of radius in IR 2 (R)). is bounded as
(() S (1 (1+ 2R
32

---

(e(a) & ((=3))
0.6
Minn (a) cl1(a-3)
Probability (x (a))
-inn-1 (a) X C
0 -1-(a-3)
0.4
0.2
Q2
03
45
Action (a)
Figure 3: Comparison of linear and quadratic softmax policies with A -5 actions and features
((a) = a 3.
D On the guarantees of misspecified BC in linear Q" rrealzzabe MDPs
It is natural to question whether existing bounds for behavioral cloning (BC) in misspecified settings (e.g., Rohatgi al., 2025; Foster al., 2024) offer satisfactory sample complexity guarantees for imitating an arbitrarily complex expert within linear Q" -carliaiz MDP. This section presents negative result, demonstrating that the approximation emrr incurred by BC, when restricted to linear softmax policy class (denoted Ii,), can be large even in simple linear Q rralizzabe MDP.
Consider single-state MDP defined follows. Let A E N be the number of actions, with the action space A = (1, A}. For each action E A, there a scalar feature (p(a) = A + a E I.
2
To ensure the MDP is linear Q* Q"-realizable, the true reward function is T'me (m)e(a) (v((a) for some
parameter Ç E R unknown to the learner. We define softmax quadratic expert policy m. as
exp (ap({p(a)²)
(a
ESEA exp (p(b)²)
This expert policy assigns the highest probability extremal actions (i.e., a and A). In contrast, linear softmax policies Hin (which are commonly used for BC in feature-based settings) are inherently designed to produce monotonie probability distributions over the action space when features are ordered (i.e., for actions a, a' E A with a' a, either (a) I π (aa)) ) or T(a) 2 π (aa)). Consequently, for A 2, no policy in Πī can achieve small Hellinger distance to this softmax quadratic expert. We illustrate this in Figure 3, where we compare the softmax quadratic expert with two linear softmax policies. Due to the monotonicity constraint, the linear softmax policies are unable to approximate the expert policy everywhere.
remains an open question whether behavioral cloning analyses can be refined to better leverage the underlying MDP structure in such misspecified scenarios. Specifically, for the constructed example, would be advantageous the misspecification error existing bounds were characterized in terms of feature expectations (e.g., EaEA 7 (a))((a) rather than state-action distributions.
33

---

E
Additional experiments
E.1 BC with a simple expert class can outperform SPOIL
We consider a linear MDP (which is a special case of linear (eraliiizab)l)yy) with features of dimension d 3. The expert class, denoted by 11 smalll is the class of softmax linear policies with features corresponding to the linear MDP features. That is, BC is given the most compact representation possible. On the other hand, the Iaine class is created using the linear MDP features, plus set of 20d redundant features. It follows that the complexity of the Q function class is larger than the expert policy function class and therefore BC is expected to outperform SPOIL on this instance. This fact is confirmed by the experiment shown in Figure
T E IT
lin,small Q" E 2 lange
100
Return
90
80
SPOIL
70
Expert
250
500 Epochs
750
1000
Figure 4: Instance in which BC with simple expert class outperform SPOIL.
E,2 Comparison with IQ-Learn in the linear case
We make comparison with IQ-Learn in the Linear MDP described in Section 5. In this experiment, we consider a linear Q-function class for both SPOIL and IQ-Learn, the environment has this structure. The results in Figure 5 show that, like SPOIL, IQ-Learn's 's performance is unaffected by the complexity of the expert class. However, SPOIL still reaches a higher cumulative reward this environment. To ensure this is fair comparison, we used the same learning rate for the policy updates SPOIL and IQ-Learn. Moreover, we tested different choices for IQ-Learn's critic learning rate, and report here the best results we could obtain.
TE E IT
TE E IT NN
70
68
Return
65
Return
64-
60
SPO11
60
55
107
56
Expect
Espes
52
250
500 Epochs
750
1000
250
500
750
1000
Epochs
Figure 5: Experiments in continuous-state domains. Curves are averaged across seeds.
E.3
Omitted experimental details
For the first experiment shown in Figure 1, one may wonder if the underperformance of behavioural cloning might be due to underoptimizing the empirical lig-likel We have ruled out this possibility by going into great lengths to optimize the likelihood, and fact the log-likelihood has approached its minimum value of zero very closely in our experiment (meaning that the probabilityy assigned to the actions seen in the expert dataset almost 1). For this optimization task, we have used Adam with default parameter settings. For the experiments in Figure 2, algorithms
34

---

implemented using shared neural network architecture consisting of layers with 64 neurons per layer. This architecture matches the one used for experiments in the same environments by Garg et al. (2021). For behavioral cloning, we employ separate three-layer multilayer perceptron with 128 neurons per layer. Implementations of IQ-Learn and P'IL utilize their original hyperparameter configurations reported in their respective publications. All networks are optimized using the Adam optimizer (Kingma and Ba, 2014) with a learning rate x 10 and default momentum parameters (31 0.9, $2 0.999). The implementations are built using PyTorch (Paszke et al., 2019).
For algorithms with primal-dual structure (i.e., IQ-Learn, P'IL and SPOIL). the policy update performed using a Soft DQN-style update (c.f. Haarnoja et al., 2017) with fixed temperature parameter. These three algorithms thus only differ in terms of their Q-value updates, and thus this experiment serves to assess the effectiveness of the novel critic loss introduced in this work.
35

---

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: Yes, the claims made in the abstract and introduction are supported by sample complexity bounds and experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the limitations are discussed in the conclusion where we also present possible ideas top overcome such limitations.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
36

---

Answer: [Yes]
Justification: Yes, the main proof ideas are clearly explained in the main text in the Analysis section and full proofs are given in the Appendix.
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 in 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 a short proof sketch to 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, the proofs are explained the best of our clarity and should be easy to follow for researchers in the field. Also the experiments are explained in enough details to be reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require 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
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 or 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 verifying the results.
37

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Yes, the code is added in the supplementary material and available online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.c cc/
connccyyl)) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" 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: / //nips. cc/
cctpccccppcccccccccccccccccccccl public/ /gwgides//////eeeeeeooo SCons///ddeSummiiiia SasSuubbsssss aassonnPllle onnoliccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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 the paper) is 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: Yes, all enviromments are standard and known in the RL community. So the experiments should be understandable by RL researchers.
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 be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, we include results averaged over 10 seeds.
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, or 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).
38

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is 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 figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: Our experiments are small scale and can be run on a laptop in within 1/2 days.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : //nuurip.s... httppplc//ttittcuiiddeeoooopppee
Answer: [Yes]
Justification: Yes, this work is aligned with the NeurlPS Ethics Guidelines.
Guidelines:
The answer NA means that the authors have 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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This work is fundamental. We do not expect direct impact on the socicty.
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.
39

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 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 (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms 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: NA.
Guidelines:
The answer NA means that the paper poses 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 we encourage authors to take this into account and make best faith effort.
12. Lieenses 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: Yes, cite all relevant works.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
40

---

If this information is not available online, the authors are encouraged to reach out to the asset'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: NA.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel 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: NA.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 the main paper.
According 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
41

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: NA.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https / //tp:///neuu..peeeeee /c//////eoeeeeecc/////////// for what should or should not be described.
42


Reviews:
[{"review_id": "0HXQUYKYTO", "reviewer": "Reviewer_dNPr", "summary": "This paper considers the problem of imitation learning when the expert policy may not be realizable by the policy class at hand. The authors propose an alternative view via Q-functions, where instead the core structural assumption made is that any policy's corresponding Q function is realizable. Under this structural hypothesis, imitation learning can be cast as a Q-learning-like problem without directly imposing policy realizability. In particular, successfully solving the saddle-point problem of minimizing a policy that achieves low worst-case Q-error with respect to the expert. Sample complexity bounds are provided for this alternate procedure and simple numerical experiments demonstrate it can outperform naive behavior cloning.", "questions": "It would be helpful to clarify some of the above points under Weaknesses. Besides that, I have a question out of curiosity: when lacking reward labels, is this method compatible with inverse reinforcement learning? If not, what are the potential theoretical barriers?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, this paper introduces an interesting alternative perspective to imitation learning, where direct realizability of the expert policy can be avoided by instead considering the induced Q-functions of the policies. The analysis and interpretations in this paper make me lean toward acceptance.\n\n### Strengths\n\nThe paper tackles a tenuous aspect of imitation learning theory in policy realizability. It is demonstrated that Q-realizability can be somewhat more natural of an assumption. Given the imitation learning objective is to achieve low reward suboptimality, the performance difference lemma demonstrates it suffices to mimic the Q function of the expert. The resulting objective function and ensuing analysis are to my knowledge novel and somewhat appealingly straightforward, which indicates that the ideas in this paper may be useful downstream.\n\n### Weaknesses\n\nThe overall observation that imitation learning can be reduced to a fitting Q-functions is not necessarily new, see e.g. [1] which is discussed in the appendix related work. However, considering the similarities in the key object of study, these works should be explicitly discussed in the main paper.\n\nThough the proposed method presents various advantages to other offline imitation learning methods, it is mentioned that policy-based methods may see advantages in other settings where the policy class is simple and the environment is difficult. It may be pedagogical for the camera-ready to provide a simple example where this is the case. Orthogonal to this nuance, a rather trivial observation of when policy-based methods such as BC are advantageous is when expert demonstrations do not carry reward labels, which deserves a bit of discussion, as a potential advantage of IL over RL is that it can be agnostic to rewards (and as such reward optimality).\n\nAs a bibliographic note, the paper [2] mentioned in the appendix related work, which considers imitation learning over continuous action spaces, demonstrates exponential-in-horizon error cannot be improved in general, actually includes any algorithm including reward-based ones, as long as the demonstration distribution is unchanged (i.e. offline IL).\n\n[1] Swamy et al. \"Of Moments and Matching: A Game-Theoretic Framework for Closing the Imitation Gap\"\n\n[2] Simchowitz et al. \"The Pitfalls of Imitation Learning when Actions are Continuous\"", "was_revised": true, "final_justification": "This paper introduces some interesting theory-oriented ideas for understanding imitation learning via induced Q-functions rather than searching directly over policies. This has certain implications when the Q-class is \"simpler\" than the policy class.\n\nThere are some concerns expressed about the scale of the experiments, but I see the experiments mostly serving the purpose of justifying the theoretical mechanisms presented in the paper more so than promote a ready-for-deployment pipeline, and therefore am satisfied with them (including the ones presented in the rebuttal).\n\nI think the (RL) theory community may find use of these results, and therefore recommend accept (5).", "rebuttal": "Thank you for your positive review, encouraging words, and insightful feedback! We answer the points you raised below.\n\n**Regarding some related work**. We will move the detailed comparison with Swamy et al. [1] from the appendix to the main body in the next version (taking advantage of the additional page allowed after acceptance).\n\nMoreover, we can also clarify the comparison with Simchowitz et al. [2]. As you noted, their work shows an unavoidable exponential-in-horizon error for offline IL *in general*. However, as we write in lines 540-545, their lower bound can be broken if the environment has structure. Although our algorithm is presented for discrete actions, we believe it could be adapted to continuous action problems by replacing the Mirror Ascent step in the policy update with continuous exponential weights (or discretizing the action set to a fine level).\n\n**Regarding a scenario favorable to BC**. As you suggested, we have run an experiment in which using BC should be more sensible than using SPOIL. More specifically, we consider a linear MDP (a special case of linear $Q^\\pi$-realizable MDPs) with features of dimension $d=3$. The expert class, denoted $\\Pi^E_{\\mathrm{lin, small}}$, is the class of softmax linear policies with features corresponding to the linear MDP features, meaning BC is given the most compact representation possible. On the other hand, the Q-function class, denoted $\\mathcal{Q}_{\\mathrm{lin, large}}$, is made artificially complex: we take the linear MDP features and add a set of $20 d$ redundant features. It follows that the complexity of the Q-function class used for SPOIL is larger than the complexity of the policy class used for BC, and therefore BC is expected to outperform SPOIL on this instance.\n\nThe following table reports the expected cumulative reward for the policies learned by SPOIL and BC after the number of epochs given in the column header. Notice that BC achieves a larger expected cumulative reward, as expected in this case.\n\n|        $\\pi_E \\in \\Pi^E_{\\mathrm{lin,small}}, Q^\\pi \\in \\mathcal{Q}_{\\mathrm{lin,large}}$          | Epoch 10 | Epoch 50 | Epoch 100  | Epoch 250\n| :------------ | :-------------- | ---------------: | ---------------: |  ---------------: |\n| SPOIL   |   64.67 ± 0.16    |    70.95  ± 2.43    | 81.51 ± 6.50  | 90.36 ± 9.62   |\n| BC   |   70.66 ± 2.06    |    83.37  ± 5.90    | 88.51 ± 7.32  | 92.53 ± 8.57   |\n\n**Comparison with inverse reinforcement learning:** Inverse Q-learning methods, such as SPOIL, have distinct trade-offs with inverse reinforcement learning (IRL).\n- On the \"pro\" side, SPOIL operates under weaker structural assumptions compared to IRL methods (e.g., $Q^\\pi$-realizability instead of the more restrictive linear MDP assumption often used in IRL), and works entirely offline, whereas IRL methods typically require online environment interaction.\n- On the other hand, SPOIL requires state-action pair observations. In scenarios with more limited information, such as observing only reward features, some IRL methods (e.g., [3, 4]) are more applicable. Both SPOIL and BC are reward-agnostic in that they learn from demonstrations without needing reward labels. The key difference is that SPOIL adopts a value-based approach to match performance, while BC uses supervised learning to match behavior.\n\nThanks again for your feedback. We are available for any further questions.\n\n**References** \n\n[3] Ziebart, B. D. (2010). Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University. Section 6.2.\n\n[4] Syed, U., and Schapire, R. E. (2007). A game-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 20."}, {"review_id": "FeLAdbaX6I", "reviewer": "Reviewer_UYBH", "summary": "This paper studies the problem of offline imitation learning in MDP given a dataset of state action pairs of expert policy. This paper relaxes the assumption of expert policy belonging to a known class to the learner and introduces a new algorithm for the class of linear $Q^{\\pi}$-realizable MDPs that guarantees to match expert performance up to $\\epsilon$ with access to $\\mathcal{O}(\\epsilon^{-2})$. Furthermore, they extend their results to non linear setting but with a worse sample complexity. Finally, they conduct empirical evaluations on their algorithms.", "questions": "Questions:\n- why on Figure 1, the BC agents doesn't improve much with complex policy class?\n- can you run IQ-Learn in linear Q environments as well to see its performance against proposed algorithms?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Quality: this paper is technically sound with support of theory and experiments.\n- Clarity: paper is well presented with assumptions, theorems, algorithms and experiments.\n- Significance: This paper relaxes a common assumption that expert policy is known to the learner and provides algorithms in both linear and non lineaner $Q^{\\pi}$-realizable MDPs with theoretical guarantees.\n\nWeaknesses:\n- Originality: the novely mainly lies in the proof, the design of the algorithm is primal-dual style, which is similar to previous work of \"Iq-learn: Inverse soft-q learning for imitation\"", "was_revised": true, "final_justification": "This paper is both theoretical and empirical solid. \nMy questions regarding comparing against IQ Learn in linear setting is resolved, and the proposed algorithms demonstrate superior performance. Hence I recommend acceptance.", "rebuttal": "Thank you for reviewing our work and for your positive evaluation. We are happy to address your questions below.\n\n**Regarding the performance of BC**. While the BC agent successfully minimizes the training loss, the dataset is not large enough for it to generalize well. Without discovering the simpler underlying linear structure of the environment, it cannot select good actions in states that were not (or sparsely) represented in the expert data, hence its poor performance.\n\n**Regarding a comparison with IQ-Learn**. In response to your question, we have run some additional experiments and implemented IQ Learn for both settings corresponding to two expert policies (the softmax linear policy and the neural network policy). We used a linear Q-function class for both SPOIL and IQ-Learn, as the environment has this structure. The results below show that, like SPOIL, IQ-Learn's performance is unaffected by the complexity of the expert class. However, SPOIL still reaches a higher cumulative reward in this environment.\n\nTo ensure this is a fair comparison, we used the same learning rate for the policy updates in SPOIL and IQ-Learn. Moreover, we tested different choices for IQ-Learn’s critic learning rate, and we report here the best results we could obtain. The results are in the following tables, where we report the expected cumulative reward achieved by the three algorithms after the number of epochs reported in the column headers.\n\n|        $\\pi_E \\in \\Pi^E_{\\mathrm{lin}}$          | Epoch 10 | Epoch 50 | Epoch 100  | Epoch 250\n| :------------ | :-------------- | ---------------: | ---------------: |  ---------------: |\n| SPOIL   |   53.78 ± 0.15    |    61.68  ± 0.90    | 65.37 ± 2.09  | 67.62 ± 2.86   |\n| BC   |   52.78 ± 0.20    |    56.26  ± 0.89    | 59.37 ± 1.52  | 63.98 ± 2.40   |\n| IQ Learn   |   52.61 ± 0.26    |    56.20  ± 1.85    | 59.08 ± 2.96  | 61.57 ± 3.62   |\n\n|        $\\pi_E \\in \\Pi^E_{\\mathrm{NN}}$          | Epoch 10 | Epoch 50 | Epoch 100  | Epoch 250\n| :------------ | :-------------- | ---------------: | ---------------: |  ---------------: |\n| SPOIL   |   53.64 ± 0.20    |    60.35  ± 1.73    | 63.06 ± 2.99  | 64.71 ± 3.77   |\n| BC   |   51.74 ± 0.09    |    52.30  ± 0.23    | 52.72 ± 0.40  | 52.99 ± 0.52   |\n| IQ Learn   |   52.56 ± 0.26    |    55.66  ± 1.58    | 58.10 ± 2.61  | 60.29 ± 3.32   |\n\nThank you again for your feedback. We are happy to discuss further if needed."}, {"review_id": "uNNV9oYG76", "reviewer": "Reviewer_Mw96", "summary": "In this paper a core challenge in imitation learning is addressed, inconsistent expert behavior. Rather than assuming the expert policy lies within a known class of optimal policies, a common but often unrealistic assumption especially in scenarios where expert behavior may be irrational, or influenced by external factors (as with human experts). This issue is known as misspecification. To address this, the authors propose a formulation that avoids step-by-step behavioral imitation and instead aims to match the expert's performance outcome. This frees the learning agent from inconsistent behaviors that may be apparent in the expert policy and focus instead on learning policies that achieve comparable returns.\n\nThe proposed algorithm, SPOIL (Saddle-Point Offline Imitation Learning), is based on an actor-critic model structured as a min-max optimization of an empirically defined loss function to that fits the previous narrative. The authors implement this approach for both linear Q-functions, which are straightforward to analyze and allow efficient closed form updates; and for general function approximators, such as neural networks, which are more flexible and realistic but require optimization and introduce additional computational complexity.\nThey provide experimental results, first comparing both variants of SPOIL to BC in a controlled MDP environment to showcase its training and final converging superiority, and then proceed to standard gym environments, showcasing their performance with different sizes of expert data in contrast to other high-performing approaches.", "questions": "1. Can you elaborate on your experimental results? \n\n2. What are the key differences with each one of the baselines?\n\n3. In which ways are the observed improvement of your algorithm significant?\n\n4. Can you comment on the lack of experiments in other, less toy, domains?\n\nSuggestions:\n\nMore challenging environments like Mujoco or Atari games would better fit your narrative. The authors could also take a look at this survey paper for environments used in imitation learning: https://arxiv.org/abs/2404.19456\n\nA simple example could have helped clarify the core idea early in the introduction.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The approach has an interesting premise, especially as the community strives to get closer to a more realistic representation of imitation learning, where there is a plethora of ways for policies to get inconsistent or unstructured in general.\n\n2. Solid theoretical work, supported by well-structured theoretical analysis, including performance guarantees\n\n3. The SPOIL algorithm is appropriate for the presented problem, including both a linear version that is easier to implement and observe results, as well as a more general version for modern deep learning approaches. \n\n4. The structure and presentation of the paper is clear and overall straight forward.\n\nWeaknesses\n\n1.\tThe authors present experimental results, but there’s little explanation of what are the main differences between SPOIL and the baseline methods used.\n\n2.\tThe chosen environments are all toy environments, simple by their nature and low dimensional. These are fine for initial testing but not enough to support broader claims, especially when making state-of-the-art comparisons. \n\n3.\tSince the authors compare their work to BC, it would be fitting to also discuss how SPOIL handles or is affected by covariate shift.\n\n4.\tThe introduction packs in a lot of background without examples or intuitive explanations.", "was_revised": true, "final_justification": "I appreciate the authors clarifications in the rebuttal. The main issue remaining in my opinion is that they have experimented with small-scale / toy experiments only. Moreover, many clarifications they provided should have been in the paper to begin with - in case of acceptance, they must be included.", "rebuttal": "Thank you for your feedback and for recognizing the solid theoretical work and clear structure of our paper. We address your questions and clarify the scope of our contributions below. We would be grateful if you might consider increasing your score in case you are satisfied with the answers.\n\nBefore providing specific clarifications to your points, let us emphasize that our work should mostly be appreciated for the theoretical contributions. The experiments serve as a proof-of-concept to demonstrate that SPOIL can be applied in practice and is competitive with modern baselines such as IQ-Learn [1] (at least in the environments we tested, which are the same as the ones used for the offline experiments in [1]). Furthermore, our approach comes with strong performance guarantees that are rigorously proved under crisply stated conditions that are common in today’s RL theory literature.\n\n**Answers to the points raised in \"Weaknesses\"**\n\n**1. Explanations of the baselines**. Due to space limitations, we omit the descriptions of the baselines (IQ-Learn and PPIL) and refer to the respective original papers [1, 2] for the complete descriptions.\n\n**2. Regarding the scale of the experiments**. Given our compute constraints, these are the environments we could test on. The selected continuous control environments (CartPole, Acrobot, LunarLander) are standard benchmarks used for offline IL algorithm evaluation in the papers we compare against, including IQ-Learn and PPIL. We believe we did not make any unreasonably broad claims about state-of-the-art performance based on the experiments, but if some part of the text gave this impression, we are happy to revise it to ensure we do not make overstatements. We nevertheless would like to reiterate that we regard our theoretical results as the main contribution of this work, and those are state-of-the-art.\n\n**3. Regarding covariate shift**. We think that by covariance shift the reviewer means the fact that BC, when analyzed via a reduction to supervised learning like in [3, Theorem 2.1], has suboptimality which is $H^2 \\epsilon_{SL}$ where $\\epsilon_{SL}$ is the generalization error in supervised learning. \nWhile the idea of reducing a learning problem to a computational oracle (i.e. empirical risk minimization) is attractive, it has its limitations. Such reductions typically yield upper bounds on the sample complexity by translating an existing sample complexity bound for a simple setting (e.g., regression) to a more complicated setting (e.g., imitation learning) at the cost of some multiplicative factors (such as the $H^2$ in [3, Theorem 2.1]). This \"black-box\" approach does not always lead to tight guarantees, as one can plausibly do better by directly addressing the complicated setting (e.g., imitation learning) more directly, without pessimistically translating the worst-case errors from one setting to the next. \nOur work analyses bypasses the reduction to supervised learning and therefore the  covariate shift phenomenon. A second advantage of our analysis is that it does not require to assume that $\\epsilon_{SL}$ is small to have small suboptimality with respect to the expert policy. It directly quantifies the number of expert demonstrations needed to achieve the desired suboptimality level $\\epsilon$.\n\n**4. Regarding the intuition**. Thanks for the suggestion! We will add some additional intuitive explanations.\n\n**Answers to the questions**\n\n**1. Regarding the experimental results**. The first experiments show that BC and SPOIL perform similarly if the complexity of the expert policy class and state-action values class is comparable. On the other hand, SPOIL performs much better when the state-action value class is simpler than the expert policy class. The second set of experiments in Section 5.1 shows that SPOIL can be used in continuous state environments with neural network function approximation, achieving comparable or better performance than the baselines.\n\n**2. Differences with baselines**. PPIL and IQ-Learn differ considerably from our method because they use different objectives to update the Q-value (or a different \"critic\" update in deep RL jargon).\n\n**3. Significance of the improvements**. As stated, our algorithm has strong improvements when the Q-function class is much simpler than the expert policy class (see Experiment 1). In the control experiments, SPOIL is either better (see Acrobot) or on par with IQ Learn and PPIL.\n\n**4. Scale of the experiments**. We were limited to small-scale experiments due to the lack of computational resources, but we believe that these experiments were sufficient to convey the message of the paper. We do think that it would be interesting to conduct large-scale experiments with SPOIL for Atari, MuJoCo, and LLMs SFT, but we had to leave this for future work.\n\nWe hope this response clarifies the contributions and context of our work. We believe our paper offers a relevant theoretical advance, supported by targeted and sound experiments. Thank you again for your time and constructive feedback.\n\n**References**\n\n[1] Garg, D., Chakraborty, S., Cundy, C., Song, J., and Ermon, S. (2021). Iq-learn: Inverse soft-q learning for imitation. Advances in Neural Information Processing Systems, 34, 4028-4039.\n\n[2] Viano, L., Kamoutsi, A., Neu, G., Krawczuk, I., and Cevher, V. (2022). Proximal point imitation learning. Advances in Neural Information Processing Systems, 35, 24309-24326.\n\n[3] Ross, S., and Bagnell, D. (2010, March). Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics (pp. 661-668). JMLR Workshop and Conference Proceedings."}, {"review_id": "QLZzDg6I0G", "reviewer": "Reviewer_UNX4", "summary": "The RL imitation learning problem is considered where a dataset is provided based on an expert policy and the objective is to output a policy whose expected return is nearly as large. Previous works assumed that the expert policy belonged to a policy class which was given to the learner and provided bounds based on the complexity of the policy class. This work instead considers an assumption on the structure of the MDP, namely that the state-action value function of all policies belong to a function class ($Q^\\pi$-realizability) given to the learner. The authors prove that their algorithm (SPOIL) requires samples from the expert policy that scales polynomially in the quantities of interest. This result is interesting because there exist MDPs that satisfy the $Q^\\pi$-realizability assumption; however, a complex policy class can be defined, which implies that the SPOIL algorithm will require less samples than previous policy based algorithms. The theoretical results are supported with experiments.", "questions": "Please see the Weaknesses section above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "$\\textbf{Strengths:}$\n1. The contribution is clearly stated and compared to previous results.\n2. The work provides the first positive result under the $Q^\\pi$-realizability assumption, which is a weaker structural assumption than previous works.\n3. Experiments are provided supporting the theory.\n\n$\\textbf{Weaknesses:}$\n1. I think the performance difference lemma (Lemma 1) should have a factor of $1/(1-\\gamma)$ multiplying the right side of the equality based on the current definition of $\\rho^\\pi$. However, I think that $\\rho^\\pi$ was meant to be defined with a factor of $(1-\\gamma)$ in front since that is how it is used throughout (for instance see the equation below line 148). I did not go through all the proof details in the appendix; however, if $\\rho^\\pi$ is indeed incorrectly defined then the authors should make sure this does not affect their final result, or update it appropriately.\n2. Does Assumption 1 need realizability of $\\textit{all}$ policies, or is it enough to have it for just stationary policies, which I think is more commonly assumed? \n3. The norm notation $||\\cdot||$ is used in Assumption 1 but I do not think it is defined anywhere. I suspect it is the 2-norm, but it should be made explicit.\n4. The objective (eq 2) is very similar to that of offline policy optimization. It seems that a result from the offline policy optimization setting would imply a result in the imitation learning setting since there the policy $\\pi$ that is output satisfies $|\\max_{\\pi'}\\rho^{\\pi'} - \\rho^\\pi| \\le \\epsilon$. It would be useful if a discussion could be added (at least in the appendix) about how the offline imitation learning setting relates to the offline policy optimization setting.\n5. There are multiple typos that should be fixed. For example: Line 287, Line 327, Line 336\n6. The conclusion states the work does not require trajectory access while some other works do. I think this is the first time trajectory access is discussed in the paper and it is challenging to understand what is meant by trajectory access and why previous works needed this since it is not mentioned in the body. It would be helpful if trajectory access was discussed in more detail in the body when comparing to previous results.", "was_revised": true, "final_justification": "The authors have addressed all of my concerns. The work provides the first positive result under the $Q^\\pi$-realizability assumption. The assumption is very commonly considered in other works and thus will be an interesting result to the RL theory community.", "rebuttal": "Thank you for your encouraging review and your careful reading of our paper! Please find our answers below.\n\n1. You are correct, there are some inconsistencies with the effective horizon factor that we have also noticed. They will be fixed in the final version.\n2. The realizability assumption only needs to hold for the policies generated by SPOIL, not for all possible policies. In the linear setting, this amounts to requiring realizability only for the softmax linear policies. This is a significantly milder requirement than in related RL theory works, which assume linear $Q^\\pi$-realizability (e.g., [1, 2]). Moreover, we do not require the realizability of the expert Q value. We will add a remark on this in the main text.\n3. Yes, it is the Euclidean norm; we will define it explicitly.\n4. The key difference is that in offline policy optimization, the learner observes a dataset containing the rewards of the observed state-action pairs. The rewards are not observed in offline imitation learning. We will comment on these differences in the related works section.\n5. Thank you for spotting these! We will fix them.\n6. This is a good point; we will explain more carefully what we mean by trajectory access.\n\nThank you again for your valuable feedback. We are happy to discuss further if you have any other questions.\n\n**References**\n\n[1] Weisz, G., György, A., and Szepesvári, C. (2023). Online RL in Linearly $q^\\pi$-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore. Advances in Neural Information Processing Systems, 36, 59172-59205.\n\n[2] Mhammedi, Z.. (2025). Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions. Thirty Eighth Conference on Learning Theory."}]

Author rebuttal:

Meta-review: The paper introduces a new bound for the performance of a policy learned in the offline imitation learning setting. It makes an important structural assumption (for a policy, the q function of a state-action tuple is a dot product of some feature of state-action tuple and some vector). It also provides a (weaker) result under less restrictive assumptions. 

The main strength of the paper is it addresses an important subproblem in the offline IL community.

The main weaknesses is the lack of extreme novelty (novelty is sufficient overall though).

Overall, this paper should be accepted because it solves an important problem well.

The discussion focussed on: (1) novelty (2) the fact that we don't observe rewards (3) covariate shift.
Decision: Accept (poster)