Value-based imitation learning is a new approach to eliminate assumptions about the policy class. We study offline imitation learning where expert realizability is replaced by Qπ-realizability. The objective is to find a policy with a return at least as good as the expert's. Our proposed algorithm, ILeNA, obtains a sample complexity in O((1−γ)4ϵ2logN(Q)) under general Qπ-realizability, and O~((1−γ)4ϵ2d) under linear Qπ-realizability. This solves the open problem of obtaining sample complexity in the order of ϵ−2 under non-convex action-value functions sets. The best previous sample complexity in the general non-convex case was in O(ϵ−4), which is improved by a factor of O((1−γ)4ϵ21) in this work. We reduce the problem to a two-player repeated game between an actor (π-player) and a critic (Q-player), and translate any no-regret dynamic between the players into a guarantee for the value of the output policy. The generality of this result enables us to use an appropriate pair of no-regret algorithms for the two players, which gives us the aforementioned sample complexity. We also support our theoretical result with numerical experiments.
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.Reviewer_rjhkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary
This paper studies value-based imitation learning, under the setting that the objective is to propose a policy whose value is as high as the expert policy's. The paper approaches the problem through a reduction to a game between the policy player and the Q-value player, where the policy aims at minimizing the value gap with the expert under the Q proposed by the Q-player and the Q-value player aims at maximizing the gap. Then the paper consider RDBR, rather than the traditional FTRL, for the regret minimization problem. This leads to a sample complexity of O(d(1−γ)−4ϵ−2), improving previous results by a factor of (1−γ)−4ϵ−2).
Critical strengths
The paper proposes a new algorithm for value-based imitation learning and yields a substantiative improvement over previous best results
The paper is generally clearly written, with sufficient discussion about how the improvement is achieved
Critical weaknesses
I do not see any major weakness of this paper. Some of my minor concerns are listed below
The paper does not provide or cite a lower bound on this problem. Therefore it is unknown that whether there is still space for algorithmic improvement
The paper studies a very specific setting, value-based imitation learning, under Qπ-realizability, which makes the scope of the paper somewhat narrow.
First, a note on the revision. The general-case analysis of the submitted version contained an error, which we have fixed. The fix makes the algorithm simpler and the proof shorter: the game is now played in a single pass over the data, and an online-to-batch argument needs no coverage over the actor’s policies, which allows us to obtain the ϵ−2 sample complexity. Appendix E summarizes all changes. We would be grateful if you could take a look at the revised version, even though the discussion period is about to end.
Why the revised version is stronger
Sample complexity. The claimed O(ϵ−2) rate now holds, with a better covering precision: ϵ(1−γ)/4 instead of ϵ2(1−γ)4/(2304A).
Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3). The total computation is O(τAN(Q,ϵ′)), where ϵ′=ϵ(1−γ)/4.
The lesson. The paper now carries an interesting message: online-to-batch on the data can be strictly stronger than estimating the loss by L^ and solving the empirical saddle-point problem. The saddle-point route needs uniform concentration over both arguments, including the solver’s policies. In the online-to-batch approach, however, each policy of the actor is evaluated only on a sample it has not seen, so the actor’s policies are never covered, and only logN(Q) enters the bound (Remark 3.3). This means that the online-to-batch technique can be both statistically and computationally stronger than estimating the loss function and solving the saddle-point problem with no-regret algorithms.
Linear case. The linear case of the submission was sound. For uniformity, it now uses the same one-pass algorithm (Theorem 5.4), giving a dimension-free bound.
Experiments. They are rerun with the corrected algorithm (Appendix C).
Lower bound. A simple two-point argument shows that the ϵ−2 rate cannot be improved. Consider a single state with a self-loop, two actions, and two candidate rewards r=(1,0) and r′=(0,1). The class Q={r+c1,r′+c1:c∈[0,γ/(1−γ)]} is Qπ-realizable under either reward. Since the data do not reveal which reward is true, the output policy must match the expert’s probability p of playing action 1 to within ϵ(1−γ). Distinguishing p=1/2±2ϵ(1−γ) requires Ω(log(1/δ)/(ϵ2(1−γ)2)) samples. The optimal dependence on 1/(1−γ) and on logN(Q) remains open, and we list it as future work (Appendix D.3).
Scope.Qπ-realizability replaces the assumption that the expert belongs to a known policy class with a structural assumption on the environment. It covers linear Qπ-realizable MDPs (including linear MDPs) and sparse-reward tasks such as the tree MDP of Appendix D.1, where logN(Q) is exponentially smaller than logN(Π). We also believe that the main technical lesson, namely that a single-pass online-to-batch game avoids covering the learner’s policies, can transfer to other minimax estimation problems.
Thank you again for your time. We are happy to answer any further questions.
This paper derives a game theoretic framework for imitation learning. The authors assume an actor, which aims at finding the policy corresponding to a trajectory of state action pairs, and the critic, which aims at finding the Q function corresponding to the Q function of the trajectory of state action pairs. Then the author write this as a min max problem and propose an algorithm to solve it and they establish the sample complexity of this algorithm.
Critical strengths
The authors propose a game theoretic framework for imitation learning which is interesting.
Critical weaknesses
The main claim of the authors regarding improvement compare to the prior work is not correct. In particular, look at this paper: https://proceedings.nips.cc/paper_files/paper/2025/file/e8aafe8b2b771540af5ee68c531b4fa9-Paper-Conference.pdf
In this paper, in Theorem 4 in the appendix, the authors establish 1/\epsilon^2 sample complexity. However, their dependency on the function class is linear, which is worst than the log dependency in this paper. Furthermore, in Corollary 1 in the same paper, they establish a dependency of 1/\epsilon^2, with a logarithmic dependency on the covering number of full convex hull of the space.
writing: The authors do not have an introduction section! The paper is written badly. The assumptions are stated before the Q-function is even defined. I think proposition 2.1 can be written as a lemma rather than proposition, as it does not have much meaning. Also, the authors must bring the main results, theorem 4.4 and 4.6 higher up in the paper, as they are the main results of the paper.
Questions for authors
Assumption 0.1 does not make sense. It is always satisfied!
Thank you for your review and for the pointer to Moulin et al. (2025).
First, a note on the revision. The general-case analysis of the submitted version contained an error, which we have fixed. The fix makes the algorithm simpler and the proof shorter: the game is now played in a single pass over the data, and an online-to-batch argument needs no coverage over the actor’s policies, which allows us to recover ϵ−2 sample complexity. Appendix E summarizes all changes. We would be grateful if you could take a look at the revised version, even though the discussion period is about to end.
Why the revised version is stronger
Sample complexity. The claimed O(ϵ−2) rate now holds, with a better covering precision: ϵ(1−γ)/4 instead of ϵ2(1−γ)4/(2304A).
Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3). The total computation is O(τAN(Q,ϵ′)), where ϵ′=ϵ(1−γ)/4.
The lesson. The paper now carries an interesting message: online-to-batch on the data can be strictly stronger than estimating the loss by L^ and solving the empirical saddle-point problem. The saddle-point route needs uniform concentration over both arguments, including the solver’s policies. In the online-to-batch approach, however, each policy of the actor is evaluated only on a sample it has not seen, so the actor’s policies are never covered, and only logN(Q) enters the bound (Remark 3.3). This means that the online-to-batch technique can be both statistically and computationally stronger than estimating the loss function and solving the saddle-point problem with no-regret algorithms.
Linear case. The linear case of the submission was sound. For uniformity, it now uses the same one-pass algorithm (Theorem 5.4), giving a dimension-free bound.
Experiments. They are rerun with the corrected algorithm (Appendix C).
Comparison with Moulin et al. (2025). Our claim is an O(ϵ−2) sample complexity that scales with logN(Q) for a non-convex Q. Moulin et al. leave this open: their general-case bound is O~(ϵ−4), and they list improving it as future work. Neither of the two results you mention gives this.
A bound linear in the size or covering number of the class is exponentially worse than one in logN(Q), as you note.
A bound in logN(Conv(Q)) is essentially the convex (linear) case, and for non-convex classes it can be exponentially larger. The correct-answer MDP of Appendix C.2 is an example: Q is a union of M affine d-dimensional pieces, so logN(Q)≈logM+dlog(1/ϵ), while logN(Conv(Q)) grows like (M+d)log(1/ϵ). Figure 3 shows the same effect empirically: methods that use the convexified class degrade quickly as M grows, while ILeNA, which uses Q itself, degrades slowly.
“Assumption 1.1 (previously 0.1) is always satisfied.” You are right that the class of all bounded functions satisfies it trivially, just as expert realizability holds trivially with the class of all policies. The assumption is meaningful in combination with the complexity of Q and the fact that the learner knows such a class. Examples include linear Qπ-realizability (Assumption 1.2), the tree MDP of Appendix D.1, where logN(Q) is exponentially smaller than logN(Π), and the MDP of Appendix C.2. Knowing such a function class can therefore be a notable advantage over assuming expert (policy) realizability.
Thank you again for your time, and we are happy to answer any further questions.
This paper studies offline imitation learning in discounted infinite horizon Markov decision processes, where the learner is given τ expert state action pairs sampled from μπE without access to the transition kernel or the reward function. Instead of assuming the expert policy πE belongs to a known policy class, the authors consider Qπ realizability (Assumption 0.1), assuming a known function class Q contains the action value function Qπ of every policy π, with the goal of finding a policy πˉ such that VπE(ρ0)−Vπˉ(ρ0)≤ϵ. Using the performance difference lemma, the problem is formulated as an empirical saddle point objective L^(π,Q) and reduced to an N round repeated game between an actor (π player) and a critic (Q player). The authors show that the game regret decomposes into the critic regret plus the average actor regret over the dataset, which allows any pair of no regret algorithms to bound VπE−Vπˉ through an optimization gap and a statistical gap. Building on this framework, their meta algorithm ILeNA pairs Regularized Delayed Best Responding with Lazy Hedge to claim O(ϵ−2) sample complexity for general nonconvex Q, improving over the O(ϵ−4) rate of SPOIL, and pairs Regularized Best Response with Mirror Descent to achieve O~(dϵ−2) sample complexity under linear Qπ realizability.
Critical strengths
The paper offers a clean game theoretic reduction for value based offline imitation learning and a clear diagnosis of why prior analyses for general Q suffered suboptimal O(ϵ−4) sample complexity. By decoupling the empirical saddle point objective into separate actor and critic losses (Proposition 2.1), Proposition 2.2 converts any no regret dynamic into a bound on VπE−Vπˉ without assuming convexity of Q or requiring the critic to be an exact best responder as in the previous literature, SPOIL. The paper also pinpoints the statistical bottleneck in Section 3.1: when the actor uses history dependent updates such as FTRL, the playable policy set Π~ depends on the entire N round trajectory of critic plays, which introduces an extra factor of N into the metric entropy of Π~×Q. By replacing FTRL with a quadratically regularized best response to a single critic action, the actor update becomes a Lipschitz Euclidean projection onto the simplex (Lemma 4.2), so the covering number of Π~ is controlled directly by the covering number of Q independently of N. In the linear Qπ realizability setting (Theorem 4.6), where the critic runs deterministic Mirror Descent on a convex ball, this reduction and covering argument hold and yield a sound O~(dϵ−2) guarantee.
Critical weaknesses
Weakness. Theorem 4.4 is false under its stated assumptions, and the failing step is Lemma B.10. In Lazy Hedge (Alg. 3), the Q player draws qk∼pk at the start of bucket k, plays Qn=qk for L rounds, and updates Hedge using the bucket's last cost vector hk=hkLQ (line 7). Although Regularized Delayed Best Responding (Eq. 8) delays the actor by one step so that πn responds to Qn−1, holding Qn=qk fixed across a bucket of length L≥2 means Qn−1=qk for all rounds after the first round of the bucket, and in particular πkL=RBRη(qk). The proof of Lemma B.10 applies Cesa Bianchi and Lugosi (2006, Cor. 4.2) to the bucket costs hk=hQkL, which relies on martingale concentration and requires hk to be fixed before qk is drawn. Because πkL responds to qk, the cost vector hk depends on the random draw qk, making the concentration bound invalid.
Counterexample. Single-state, self-looping MDP with three actions, r=(0,0,21), γ=21, πE=e3. Then Vπ=π(3) and Qπ=r+21π(3)1. Let Q={r+c1:c∈[0,21]}∪{(2,0,1.8),(0,2,1.8)}. This satisfies Assumption 0.1 (∥Q∥∞≤2=1/(1−γ)).
Take ϵ=0.25, δ=0.05, and the parameters in Theorem B.6. The cover radius is 1/768, and the minimal cover has 192 segment points plus the two added functions. This gives η=384, N=1.917⋅1012, L=11318, λ=1.247⋅10−4. The actor plays e1, e2 against the added functions and e3 against the segment.
After a bucket that draws an added function, the costs are 0.2 (drawn function), −1.8 (other added function), −0.5 (segment). After a segment draw, all costs are 0. So wseg/w1w2 starts at 192 and is multiplied by e−0.3λ after each draw of an added function. By AM–GM, the expected number of segment buckets is at most 96/(1−e−0.3λ). Counting round 1 and the L delayed rounds after each segment draw gives
E[πˉ(3)]≤N1+96L/(1−e−0.3λ)<0.015153.
Since VπE=1 and Vπˉ=πˉ(3), this gives E[VπE−Vπˉ]>0.98, and by Markov's inequality Pr(VπE−Vπˉ≤0.25)=Pr(πˉ(3)≥0.75)<0.0203. Theorem 4.4 claims Pr(VπE−Vπˉ≤0.25)≥1−2δ=0.9; the bound above gives <0.0203, a contradiction.
Thank you for the careful reading of Lemma B.10 and for the explicit counterexample. You are right: there was a mistake in the submitted version, and as a result, Theorem 4.4 of the submission did not hold.
We have fixed this in the revised version, and we would be grateful if you could take a look, even though the discussion period is about to end. The fix is short, and it makes the algorithm simpler and the proof shorter. Appendix E of the revised version summarizes all changes for the reviewers. In short, the game is now played in a single pass over the data, with round t using only the t-th sample. With this online-to-batch technique, we no longer need any covering of the policies played by the actor, which gives the desired ϵ−2 sample complexity in the non-convex case as well.
Why the revised version is stronger
Sample complexity. The claimed O(ϵ−2) rate now holds, with a better covering precision: ϵ(1−γ)/4 instead of ϵ2(1−γ)4/(2304A).
Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3). The total computation is O(τAN(Q,ϵ′)), where ϵ′=ϵ(1−γ)/4.
The lesson. The paper now carries an interesting message: online-to-batch on the data can be strictly stronger than estimating the loss by L^ and solving the empirical saddle-point problem. The saddle-point route needs uniform concentration over both arguments, including the solver’s policies. In the online-to-batch approach, however, each policy of the actor is evaluated only on a sample it has not seen, so the actor’s policies are never covered, and only logN(Q) enters the bound (Remark 3.3). This means that the online-to-batch technique can be both statistically and computationally stronger than estimating the loss function and solving the saddle-point problem with no-regret algorithms.
Linear case. As you noted, the linear case of the submission was sound. For uniformity, it now uses the same one-pass algorithm (Theorem 5.4), giving a dimension-free bound.
Experiments. They are rerun with the corrected algorithm (Appendix C).
Thank you again for your time. We hope the revised version addresses your concerns, and we appreciate your time. We are happy to answer any questions or clarify anything that is unclear.
From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.
Thank you for your review and comments.
First, a note on the revision. The general-case analysis of the submitted version contained an error, which we have fixed. The fix makes the algorithm simpler and the proof shorter: the game is now played in a single pass over the data, and an online-to-batch argument needs no coverage over the actor’s policies, which allows us to obtain the ϵ−2 sample complexity. Appendix E summarizes all changes. We would be grateful if you could take a look at the revised version, even though the discussion period is about to end.
Why the revised version is stronger
Lower bound. A simple two-point argument shows that the ϵ−2 rate cannot be improved. Consider a single state with a self-loop, two actions, and two candidate rewards r=(1,0) and r′=(0,1). The class Q={r+c1, r′+c1:c∈[0,γ/(1−γ)]} is Qπ-realizable under either reward. Since the data do not reveal which reward is true, the output policy must match the expert’s probability p of playing action 1 to within ϵ(1−γ). Distinguishing p=1/2±2ϵ(1−γ) requires Ω(log(1/δ)/(ϵ2(1−γ)2)) samples. The optimal dependence on 1/(1−γ) and on logN(Q) remains open, and we list it as future work (Appendix D.3).
Scope. Qπ-realizability replaces the assumption that the expert belongs to a known policy class with a structural assumption on the environment. It covers linear Qπ-realizable MDPs (including linear MDPs) and sparse-reward tasks such as the tree MDP of Appendix D.1, where logN(Q) is exponentially smaller than logN(Π). We also believe that the main technical lesson, namely that a single-pass online-to-batch game avoids covering the learner’s policies, can transfer to other minimax estimation problems.
Thank you again for your time. We are happy to answer any further questions.