acceptodds
Under review as a conference paper at ICLR 2027

ILeNA: Sample Complexity for Value-Based Imitation Learning

Abstract

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 -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 under general -realizability, and under linear -realizability. This solves the open problem of obtaining sample complexity in the order of under non-convex action-value functions sets. The best previous sample complexity in the general non-convex case was in , which is improved by a factor of in this work. We reduce the problem to a two-player repeated game between an actor (-player) and a critic (-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.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Imitation Learning, Actor-Critic, No-regret Learning, Minimax Optimization, Value-based Imitation Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
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 QQ proposed by the QQ-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)O(d(1-\gamma)^{-4}\epsilon^{-2}), improving previous results by a factor of (1−γ)−4ϵ−2)(1-\gamma)^{-4}\epsilon^{-2}).

Critical strengths
  1. The paper proposes a new algorithm for value-based imitation learning and yields a substantiative improvement over previous best results
  2. 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

  1. 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
  2. The paper studies a very specific setting, value-based imitation learning, under QπQ^\pi-realizability, which makes the scope of the paper somewhat narrow.
Questions for authors

See weakness.

2 comments

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\epsilon^{-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)O(\epsilon^{-2}) rate now holds, with a better covering precision: ϵ(1−γ)/4\epsilon(1-\gamma)/4 instead of ϵ2(1−γ)4/(2304A)\epsilon^2(1-\gamma)^4/(2304A).
  • Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3)N=\Omega(\epsilon^{-3}). The total computation is O(τAN(Q,ϵ′))O(\tau A \mathcal{N}(\mathcal{Q},\epsilon')), where ϵ′=ϵ(1−γ)/4\epsilon'=\epsilon(1-\gamma)/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^\hat{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 log⁡N(Q)\log \mathcal{N}(\mathcal{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\epsilon^{-2} rate cannot be improved. Consider a single state with a self-loop, two actions, and two candidate rewards r=(1,0)r=(1,0) and r′=(0,1)r'=(0,1). The class Q={r+c1, r′+c1:c∈[0,γ/(1−γ)]}\mathcal{Q}=\lbrace r+c\mathbf{1},\ r'+c\mathbf{1} : c\in[0,\gamma/(1-\gamma)]\rbrace is QπQ^\pi-realizable under either reward. Since the data do not reveal which reward is true, the output policy must match the expert’s probability pp of playing action 1 to within ϵ(1−γ)\epsilon(1-\gamma). Distinguishing p=1/2±2ϵ(1−γ)p=1/2\pm 2\epsilon(1-\gamma) requires Ω(log⁡(1/δ)/(ϵ2(1−γ)2))\Omega(\log(1/\delta)/(\epsilon^2(1-\gamma)^2)) samples. The optimal dependence on 1/(1−γ)1/(1-\gamma) and on log⁡N(Q)\log \mathcal{N}(\mathcal{Q}) remains open, and we list it as future work (Appendix D.3).

Scope. QπQ^\pi-realizability replaces the assumption that the expert belongs to a known policy class with a structural assumption on the environment. It covers linear QπQ^\pi-realizable MDPs (including linear MDPs) and sparse-reward tasks such as the tree MDP of Appendix D.1, where log⁡N(Q)\log \mathcal{N}(\mathcal{Q}) is exponentially smaller than log⁡N(Π)\log \mathcal{N}(\Pi). 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.

I thank the author for the responses and would like to keep my rating.

Reviewer_3oBcOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

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!

1 comment

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\epsilon^{-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)O(\epsilon^{-2}) rate now holds, with a better covering precision: ϵ(1−γ)/4\epsilon(1-\gamma)/4 instead of ϵ2(1−γ)4/(2304A)\epsilon^2(1-\gamma)^4/(2304A).

  • Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3)N=\Omega(\epsilon^{-3}). The total computation is O(τAN(Q,ϵ′))O(\tau A \mathcal{N}(\mathcal{Q},\epsilon')), where ϵ′=ϵ(1−γ)/4\epsilon'=\epsilon(1-\gamma)/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^\hat{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 log⁡N(Q)\log \mathcal{N}(\mathcal{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)O(\epsilon^{-2}) sample complexity that scales with log⁡N(Q)\log \mathcal{N}(\mathcal{Q}) for a non-convex Q\mathcal{Q}. Moulin et al. leave this open: their general-case bound is O~(ϵ−4)\tilde{O}(\epsilon^{-4}), and they list improving it as future work. Neither of the two results you mention gives this.

  1. A bound linear in the size or covering number of the class is exponentially worse than one in log⁡N(Q)\log \mathcal{N}(\mathcal{Q}), as you note.
  2. A bound in log⁡N(Conv(Q))\log \mathcal{N}(\mathrm{Conv}(\mathcal{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\mathcal{Q} is a union of MM affine dd-dimensional pieces, so log⁡N(Q)≈log⁡M+dlog⁡(1/ϵ)\log \mathcal{N}(\mathcal{Q}) \approx \log M + d\log(1/\epsilon), while log⁡N(Conv(Q))\log \mathcal{N}(\mathrm{Conv}(\mathcal{Q})) grows like (M+d)log⁡(1/ϵ)(M+d)\log(1/\epsilon). Figure 3 shows the same effect empirically: methods that use the convexified class degrade quickly as MM grows, while ILeNA, which uses Q\mathcal{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\mathcal{Q} and the fact that the learner knows such a class. Examples include linear QπQ^\pi-realizability (Assumption 1.2), the tree MDP of Appendix D.1, where log⁡N(Q)\log \mathcal{N}(\mathcal{Q}) is exponentially smaller than log⁡N(Π)\log \mathcal{N}(\Pi), 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.

Reviewer_7RQ9OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies offline imitation learning in discounted infinite horizon Markov decision processes, where the learner is given τ\tau expert state action pairs sampled from μπE\mu^{\pi_E} without access to the transition kernel or the reward function. Instead of assuming the expert policy πE\pi_E belongs to a known policy class, the authors consider QπQ^\pi realizability (Assumption 0.1), assuming a known function class Q\mathcal Q contains the action value function QπQ^\pi of every policy π\pi, with the goal of finding a policy πˉ\bar\pi such that VπE(ρ0)−Vπˉ(ρ0)≤ϵV^{\pi_E}(\rho_0) - V^{\bar\pi}(\rho_0) \le \epsilon. Using the performance difference lemma, the problem is formulated as an empirical saddle point objective L^(π,Q)\hat{\mathcal L}(\pi, Q) and reduced to an NN round repeated game between an actor (π\pi player) and a critic (QQ 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πˉV^{\pi_E} - V^{\bar\pi} 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)O(\epsilon^{-2}) sample complexity for general nonconvex Q\mathcal Q, improving over the O(ϵ−4)O(\epsilon^{-4}) rate of SPOIL, and pairs Regularized Best Response with Mirror Descent to achieve O~(dϵ−2)\tilde O(d\epsilon^{-2}) sample complexity under linear QπQ^\pi 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\mathcal Q suffered suboptimal O(ϵ−4)O(\epsilon^{-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πˉV^{\pi_E} - V^{\bar\pi} without assuming convexity of Q\mathcal 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 Π~\tilde\Pi depends on the entire NN round trajectory of critic plays, which introduces an extra factor of NN into the metric entropy of Π~×Q\tilde\Pi \times \mathcal 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 Π~\tilde\Pi is controlled directly by the covering number of Q\mathcal Q independently of NN. In the linear QπQ^\pi 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)\tilde O(d\epsilon^{-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 QQ player draws qk∼pkq_k \sim p_k at the start of bucket kk, plays Qn=qkQ_n = q_k for LL rounds, and updates Hedge using the bucket's last cost vector hk=hkLQh_k = h^Q_{kL} (line 7). Although Regularized Delayed Best Responding (Eq. 8) delays the actor by one step so that πn\pi_n responds to Qn−1Q_{n-1}, holding Qn=qkQ_n = q_k fixed across a bucket of length L≥2L \ge 2 means Qn−1=qkQ_{n-1} = q_k for all rounds after the first round of the bucket, and in particular πkL=RBRη(qk)\pi_{kL} = \mathrm{RBR}\eta(q_k). The proof of Lemma B.10 applies Cesa Bianchi and Lugosi (2006, Cor. 4.2) to the bucket costs hk=hQkLh_k = h^Q{kL}, which relies on martingale concentration and requires hkh_k to be fixed before qkq_k is drawn. Because πkL\pi_{kL} responds to qkq_k, the cost vector hkh_k depends on the random draw qkq_k, making the concentration bound invalid.

Counterexample. Single-state, self-looping MDP with three actions, r=(0,0,12)r=(0,0,\tfrac12), γ=12\gamma=\tfrac12, πE=e3\pi_E=e_3. Then Vπ=π(3)V^\pi=\pi(3) and Qπ=r+12π(3)1Q^\pi=r+\tfrac12\pi(3)\mathbf 1. Let Q={r+c1:c∈[0,12]}∪{(2,0,1.8),(0,2,1.8)}\mathcal Q=\{r+c\mathbf 1:c\in[0,\tfrac12]\}\cup\{(2,0,1.8),(0,2,1.8)\}. This satisfies Assumption 0.1 (∥Q∥∞≤2=1/(1−γ)\|Q\|_\infty\le 2=1/(1-\gamma)).

Take ϵ=0.25\epsilon=0.25, δ=0.05\delta=0.05, and the parameters in Theorem B.6. The cover radius is 1/7681/768, and the minimal cover has 192 segment points plus the two added functions. This gives η=384\eta=384, N=1.917⋅1012N=1.917\cdot10^{12}, L=11318L=11318, λ=1.247⋅10−4\lambda=1.247\cdot10^{-4}. The actor plays e1e_1, e2e_2 against the added functions and e3e_3 against the segment.

After a bucket that draws an added function, the costs are 0.20.2 (drawn function), −1.8-1.8 (other added function), −0.5-0.5 (segment). After a segment draw, all costs are 00. So wseg/w1w2w_{\rm seg}/\sqrt{w_1w_2} starts at 192192 and is multiplied by e−0.3λe^{-0.3\lambda} after each draw of an added function. By AM–GM, the expected number of segment buckets is at most 96/(1−e−0.3λ)96/(1-e^{-0.3\lambda}). Counting round 1 and the LL delayed rounds after each segment draw gives E[πˉ(3)]≤1+96L/(1−e−0.3λ)N<0.015153.\mathbb E[\bar\pi(3)]\le\frac{1+96L/(1-e^{-0.3\lambda})}{N}<0.015153.

Since VπE=1V^{\pi_E}=1 and Vπˉ=πˉ(3)V^{\bar\pi}=\bar\pi(3), this gives E[VπE−Vπˉ]>0.98\mathbb E[V^{\pi_E}-V^{\bar\pi}]>0.98, and by Markov's inequality Pr⁡(VπE−Vπˉ≤0.25)=Pr⁡(πˉ(3)≥0.75)<0.0203\Pr(V^{\pi_E}-V^{\bar\pi}\le0.25)=\Pr(\bar\pi(3)\ge0.75)<0.0203. Theorem 4.4 claims Pr⁡(VπE−Vπˉ≤0.25)≥1−2δ=0.9\Pr(V^{\pi_E}-V^{\bar\pi}\le0.25)\ge1-2\delta=0.9; the bound above gives <0.0203<0.0203, a contradiction.

Questions for authors

Please see weakness

1 comment

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 tt using only the tt-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\epsilon^{-2} sample complexity in the non-convex case as well.

Why the revised version is stronger

  • Sample complexity. The claimed O(ϵ−2)O(\epsilon^{-2}) rate now holds, with a better covering precision: ϵ(1−γ)/4\epsilon(1-\gamma)/4 instead of ϵ2(1−γ)4/(2304A)\epsilon^2(1-\gamma)^4/(2304A).
  • Computation. There is no separate number of iterations; the old analysis needed N=Ω(ϵ−3)N=\Omega(\epsilon^{-3}). The total computation is O(τAN(Q,ϵ′))O(\tau A \mathcal{N}(\mathcal{Q},\epsilon')), where ϵ′=ϵ(1−γ)/4\epsilon'=\epsilon(1-\gamma)/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^\hat{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 log⁡N(Q)\log \mathcal{N}(\mathcal{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.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.