acceptodds
Under review as a conference paper at ICLR 2027

Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning

Abstract

We study adversarial imitation learning (AIL), in which an agent learns to imitate expert demonstrations by optimizing a policy against an adversarial reward that distinguishes expert and learner behavior. Historically, reward regularization and entropy-based policy regularization are key components of empirically successful methods such as GAIL and LS-IQ, yet their finite-sample benefits remain underexplored. We establish fast rates for jointly regularized AIL in finite-horizon Markov decision processes with general function approximation. Our model-free algorithm, Dually Regularized AIL, combines KL policy regularization with a quadratic reward penalty weighted by expert and learner occupancies. With online episodes and expert trajectories, we prove a bound on the regularized imitation gap for fixed regularization parameters. Our analysis combines an online mirror descent construction for general convex reward classes to control estimation error from finite expert data and stochastic learner feedback, with a sharp analysis of optimistic KL-regularized policy learning. To the best of our knowledge, Dually Regularized AIL is the first algorithm to simultaneously achieve sample complexity in both expert demonstrations and online interactions for this regularized AIL objective, even with stochastic experts. These results provide a rigorous characterization of the complementary statistical benefits of reward and policy regularization in AIL.

Primary area:
reinforcement learning
Keywords:
Adversarial Imitation Learning, RL Theory

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_jk8iOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper investigate the benefits of combining reward and policy regularization in adversarial imitation learning. The main theoretical contribution is a fast-rate convergence guarantee for a jointly regularized AIL objective under general function approximation. The result appears technically nontrivial, particularly in its reward-learning analysis. The paper does not provide experiments and does not demonstrate the applicability of the guarantees.

Critical strengths
  1. Good theoretical contributions in particular within the reward-side analysis. I could not identify clear errors in the mathematical formulations and proofs.
Critical weaknesses
  1. Absence of practical evidences. Compared to other theoretical papers on this topic, such as [1], [2] and [3], this paper does not contain any experimental evaluation and does not demonstrate applicability of the provided results.

[1] Li, Shangzhe, Dongruo Zhou, and Weitong Zhang. "Near-optimal second-order guarantees for model-based adversarial imitation learning." International Conference on Learning Representations. Vol. 2026. 2026.

[2] Xu, Tian, et al. "Provably and practically efficient adversarial imitation learning with general function approximation." Advances in Neural Information Processing Systems 37 (2024): 66108-66146.

[3] Chen, Y, Giammarino, V, Queeney, J, and Paschalidis, IC. Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guarantees. Retrieved from https://par.nsf.gov/biblio/10692547. Transactions on Machine Learning Research

Questions for authors
  1. Would be possible to show that the theoretical strengths of the proposed algorithm translated in empirical advantages?

  2. Do the improved rates of convergence imply better imitation performance?

2 comments

We thank the reviewer for the valuable comments and the support for acceptance of our manuscript. We provide our response to the reviewer's concerns below.

W1&Q1&Q2: The paper lacks empirical validation demonstrating whether its improved theoretical convergence rates translate into practical advantages and better imitation performance.

A: We thank the reviewer for this suggestion. We have added experiments on a small tabular MDP with a stochastic expert in Appendix G of the revised manuscript, where the regularized dual gap can be computed exactly. Across 20 seeds, log–log plots against KK and NN show sustained decay with online interactions and approximately inverse-NN scaling, with fitted slopes of −0.825-0.825 and −1.023-1.023, respectively. At the same sample budget, our method achieves a substantially smaller gap than unregularized AIL under the common regularized evaluation objective. Ablations over α\alpha and τ\tau further show that stronger regularization reduces the gap under the corresponding objective within the tested range.

Regarding imitation performance, our regularized formulation and the unregularized formulations in [1–3] optimize different objectives and may therefore have different optimal solutions. Our approach trades potential regularization bias for faster convergence to the regularized optimum: for fixed positive regularization parameters, we achieve O~(1/ϵ)\widetilde{\mathcal O}(1/\epsilon) sample complexity in both expert demonstrations NN and online interactions KK for deterministic and stochastic experts under our assumptions. Such a simultaneous guarantee cannot hold uniformly for unregularized imitation learning for deterministic and stochastic experts. In particular, [1] establishes an Ω(1/ϵ2)\Omega(1/\epsilon^2) expert-sample lower bound for stochastic instances with nonvanishing variance. Our faster rates thus characterize the benefit of regularization in exchange for the bias introduced by leveraging the regularized objective.

Dear Reviewer jk8i,

Thank you again for your detailed and constructive review. As we are about halfway through the discussion period, we would like to kindly follow up.

We would like to briefly summarize our main clarifications and additional experimental results:

  • Empirical validation of convergence rates (W1 & Q1). We add tabular MDP experiments with a stochastic expert across 20 seeds, where the regularized dual gap can be computed exactly. The log–log plots show fitted slopes of −0.825-0.825 and −1.023-1.023 with respect to online interactions KK and expert demonstrations NN, respectively, broadly consistent with the predicted 1/K1/K and 1/N1/N scaling (Appendix G).

  • Comparison with unregularized AIL (W1 & Q1). Under the same regularized evaluation criterion and sample budget, our method achieves substantially smaller dual gaps than unregularized AIL. We also provide ablations showing how α\alpha and τ\tau affect convergence and the regularized objective, offering additional empirical support for the role of regularization (Appendix G).

  • Imitation performance and regularization tradeoff (Q2). We clarify that our O~(1/ϵ)\widetilde O(1/\epsilon) sample-complexity guarantees concern convergence to the regularized optimum, which may differ from the expert policy. We further derive an explicit bound on the unregularized imitation gap, with an additional bias term of τDE+αH/2\tau D_E+\alpha H/2, thereby quantifying the tradeoff between faster convergence and imitation accuracy (Appendix F).

We would greatly appreciate it if you could let us know whether our responses address your concerns, and we would be happy to clarify any remaining questions.

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

This paper studies the problem of Adversarial Imitation Learning (AIL), under the setting where both the policy side and reward side sub-problems are regularized. The authors propose Dually Regularized AIL, which combines KL-regularized (entropy regularized when using KL to a uniform dist) value iteration for the policy and online MD on the reward function under a quadratic penalty as in LSIQ.

The main result is an Õ(1/K + 1/N) bound on the regularized saddle-point gap, where K is the number of online episodes and N the number of expert trajectories, which is an improvement over the rates proven in prior work.

Critical strengths
  • The paper studies and important, and relevant quuestion: whether the inclusion of regularization in AIL improves the convergence in the number of expert demonstrations and online samples.
  • The paper is well written. The introduction gives an intuitive motivation for why regularization could yield faster rates, and it is generally upfront that its rates do not transfer to the unregularised imitation gap.
  • The analysis handles the reuse of the same expert dataset across all reward updates, without requiring a deterministic expert.
Critical weaknesses

While my impression of the paper is overall positive, there are some questions and points that I'd like to raise.

  • My main issue is that the guarantee is for the regularized objective, and it is unclear what it implies for imitation. If I understand correctly, the guarantees concern the regularized saddle point gap, not the imitation gap. Hence, the solution of the regularised problem is, in general, not the expert. While this is fine in general (see [1] for a geometric example of when the regularized optimum differs from the expert), it should nevertheless be discussed clearly. In general, my question is how does the result translate to the imitation gap or the expert’s performance?
  • Table 1 is a bit misleading given the caveats highlighted in remark 3. Can you please make it clear that your rates are only for the regularized problem.
  • My second concern is that the bounds are not validated empirically. The paper would significantly benefit from even a small-scale experiment e.g. tabular MDP where the gap can be computed. For example, plotting the dual gap against K and N on a log-log scale, comparing with unregularized AIL, and varying α and τ would show the effect of regularization on the rate and on the distance to the expert.
  • The proofs require the expert to have finite KL cost relative to π^ref, but this is only stated in the appendix (App. C). Please state it in the main text. Does this exclude reference policies that do not cover the expert's actions?

Minor

  • Sec. 3: The notation ΔS\Delta_{\mathcal{S}} and ΔA\Delta_{\mathcal{A}} (used for PhP_h and πh\pi_h) is not introduced. Please state that ΔX\Delta_{\mathcal{X}} denotes the set of probability distributions over X\mathcal{X}.
  • It might be worth discussing [1], which also studies a similar IRL problem under regularization (given that they also highlight my first point geometrically).

[1] A. Diwan, J. Peters, and O. Arenz. A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2026.

Questions for authors

Please see weaknesses

6 comments

We thank the reviewer for the valuable comments and the support for acceptance of our manuscript. We provide our response to the reviewer's concerns below.

W1. Why we use a uses a regularized performance criterion instead of unregularized version

Review comment: the guarantee is for the regularized objective, and it is unclear what it implies for imitation. If I understand correctly, the guarantees concern the regularized saddle point gap, not the imitation gap. Hence, the solution of the regularised problem is, in general, not the expert. While this is fine in general (see [1] for a geometric example of when the regularized optimum differs from the expert), it should nevertheless be discussed clearly. In general, my question is how does the result translate to the imitation gap or the expert’s performance?

Thank you for raising the connection between our regularized guarantee and imitation performance. Our guarantee concerns the regularized saddle-point gap in Eq. (1) and Corollary 1, and it translates into an imitation-performance bound with an explicitly bounded regularization discrepancy. Our objective is to characterize the statistical benefits of regularization in AIL, accounting for both finite expert demonstrations and online interactions. This focus is consistent with existing regularized RL theory: [2] establishes logarithmic regret relative to the optimum of the KL-regularized objective.

To make the implication for imitation explicit, let Jr0(π)=Eπ[∑h=1Hrh(sh,ah)]J_r^0(\pi)=\mathbb E_\pi[\sum_{h=1}^H r_h(s_h,a_h)] denote the unregularized return and define

:= \sup_{r\in\mathcal R} \bigl[J_r^0(\pi^E)-J_r^0(\pi)\bigr].$$ Write $$C(\pi):=\sum_{h=1}^H \mathbb E_{\pi}\left[ \operatorname{KL}\left( \pi_h(\cdot\mid s_h) \,\Vert\, \pi_h^{\mathrm{ref}}(\cdot\mid s_h) \right) \right], \qquad D_E:=C(\pi^E)<\infty,$$ where $C$ is averaged over the component policies for the returned episode-level mixture. If Corollary 1 gives $\operatorname{Gap}(\bar\pi_K,\bar r_K)\le\varepsilon_{K,N}$, then, on the same event, $$\boxed{ \Delta_{\mathcal R}(\bar\pi_K) \le \varepsilon_{K,N} +\tau D_E +\frac{\alpha H}{2}. }$$ This follows by using the expert as a comparator in the policy infimum: $$\inf_\pi L(\pi,\bar r_K)\le L(\pi^E,\bar r_K)=-\psi_{\pi^E}^{\omega}(\bar r_K).$$ Expanding Eq. (1), for every $r\in\mathcal R$, we obtain $$\begin{aligned} J_r^0(\pi^E)-J_r^0(\bar\pi_K) \le{} \varepsilon_{K,N} +\tau\bigl[D_E-C(\bar\pi_K)\bigr]+\psi_{\bar\pi_K}^{\omega}(r) -\psi_{\pi^E}^{\omega}(\bar r_K). \end{aligned}$$ The stated bound follows from the nonnegativity of the KL and quadratic penalties and from $\psi_{\bar\pi_K}^{\omega}(r)\le\alpha H/2$, since $|r_h|\le1$. Consequently, whenever the task reward $r^\star$ belongs to $\mathcal R$, the learned policy’s return is at most $\varepsilon_{K,N}+\tau D_E+\alpha H/2$ below the expert’s return. For a finite action space and a uniform reference policy, $D_E\le H\log|\mathcal A|$, giving $$\Delta_{\mathcal R}(\bar\pi_K) \le \varepsilon_{K,N} + H\left(\tau\log|\mathcal A|+\frac{\alpha}{2}\right).$$ A reference policy closer to the expert in expected KL gives a smaller policy-regularization contribution to this bound. **This conversion makes the tradeoff between regularization bias and convergence explicit.** Regularized and unregularized AIL optimize different objectives and may therefore have different optimal policies. The geometric analysis of entropy-regularized reverse-KL occupancy matching in [1] offers a complementary perspective on this distinction. Our approach trades potential regularization bias for faster convergence to the regularized optimum: for fixed positive regularization parameters and controlled function-class complexity, the $\widetilde{\mathcal O}(1/K+1/N)$ guarantee yields $\widetilde{\mathcal O}(1/\epsilon)$ sample complexity in both expert demonstrations $N$ and online interactions $K$, for deterministic and stochastic experts under our assumptions. Such a simultaneous guarantee cannot hold uniformly for unregularized imitation learning under general function approximation when stochastic experts are allowed. In particular, Li et al. [3] establish an $\Omega(\sigma^2/\epsilon^2)$ expert-sample lower bound, which becomes $\Omega(1/\epsilon^2)$ on stochastic instances with nonvanishing variance. This rules out a uniform $\widetilde{\mathcal O}(1/\epsilon)$ guarantee in both $N$ and $K$ for that unregularized setting. Our faster rates therefore characterize convergence for the regularized objective while allowing a potential imitation discrepancy bounded by $\tau D_E+\alpha H/2$. Taking $\alpha$ and $\tau$ toward zero reduces this discrepancy bound but increases the inverse-coefficient factors in our sample-complexity guarantees. We have added this discussion in Appendix F of our revised manuscript.

W2: Table 1 is a bit misleading given the caveats highlighted in remark 3. Can you please make it clear that your rates are only for the regularized problem.

Thanks for pointing out this issue. We have stated the criterion difference in Table 1 in our original manuscript. In our newest revision, we have revised the manuscript to make it clear that the rate is evaluated in different forms.

W3: The paper lacks empirical validation of its bounds; tabular experiments should examine dual-gap scaling with KK and NN, compare against unregularized AIL, and assess how α\alpha and τ\tau affect convergence and distance to the expert.

A: We thank the reviewer for this suggestion. We have added experiments on a small tabular MDP with a stochastic expert. Across 20 seeds, log–log plots against KK and NN show sustained decay with online interactions and approximately inverse-NN scaling, with fitted slopes of −0.825-0.825 and −1.023-1.023, respectively. We also compare with unregularized AIL under the same regularized evaluation objective, finding substantially smaller gaps for our method. Finally, ablations over α\alpha and τ\tau show that stronger regularization reduces the gap under the corresponding objective within the tested range. These experiments provide empirical support for convergence in the regularized saddle-point criterion studied by our theory. The experimental details and results are shown in Appendix G in our revised manuscript.

W4: The proofs require the expert to have finite KL cost relative to πref\pi^\text{ref}, but this is only stated in the appendix (App. C). Please state it in the main text. Does this exclude reference policies that do not cover the expert's actions?

A: Thank you for pointing this out. This is a natural requirement when using the expert as a finite-value comparator under KL regularization and usually one assumes the reference policy are supposed to cover the expert policy. For example, the KL-regularized RL objective studied in [2], written in our notation, is

Jrτ(π)=Jr0(π)−τEP,π[∑h=1HKL⁡(πh(⋅∣sh) ∥ πhref(⋅∣sh))],J_r^\tau(\pi)=J_r^0(\pi)-\tau\mathbb E_{P,\pi}\left[\sum_{h=1}^H\operatorname{KL}\left(\pi_h(\cdot\mid s_h)\,\Vert\,\pi_h^{\mathrm{ref}}(\cdot\mid s_h)\right)\right],

where Jr0(π)J_r^0(\pi) denotes the unregularized return. Thus, policies with infinite expected KL have regularized return −∞-\infty when rewards are bounded.

In particular, for discrete actions, if πhE(a∣s)>0\pi_h^E(a\mid s)>0 while πhref(a∣s)=0\pi_h^{\mathrm{ref}}(a\mid s)=0, the KL divergence contains the term

πhE(a∣s)log⁡πhE(a∣s)πhref(a∣s)=+∞.\pi_h^E(a\mid s)\log\frac{\pi_h^E(a\mid s)}{\pi_h^{\mathrm{ref}}(a\mid s)}=+\infty.

If this support mismatch occurs on a set of states with positive expert occupancy, then DE=+∞D_E=+\infty and Jrτ(πE)=−∞J_r^\tau(\pi^E)=-\infty. The divergence is particularly transparent for a deterministic expert taking action aEa_E:

KL⁡(πhE(⋅∣s) ∥ πhref(⋅∣s))=−log⁡πhref(aE∣s)⟶+∞as πhref(aE∣s)↓0.\operatorname{KL}\left(\pi_h^E(\cdot\mid s)\,\Vert\,\pi_h^{\mathrm{ref}}(\cdot\mid s)\right)=-\log\pi_h^{\mathrm{ref}}(a_E\mid s)\longrightarrow+\infty\quad\text{as }\pi_h^{\mathrm{ref}}(a_E\mid s)\downarrow0.

Therefore, yes, our assumption excludes reference policies that fail to cover the expert’s actions on expert-visited states. This is consistent with the Gibbs solution in [2, Proposition 3.5], πh⋆(a∣s)∝πhref(a∣s)exp⁡(Qh⋆(s,a)/τ)\pi_h^\star(a\mid s)\propto\pi_h^{\mathrm{ref}}(a\mid s)\exp(Q_h^\star(s,a)/\tau), which preserves the reference policy’s action support. Reference policies with partial support remain admissible when they cover the expert’s conditional action distributions and the expected KL is finite. We have stated this requirement explicitly in Section 3 of our revised manuscript.

W5: Sec. 3: The notation ΔS\Delta_\mathcal{S} and ΔA\Delta_\mathcal{A} (used for PhP_h and πh\pi_h) is not introduced. Please state that ΔX\Delta_\mathcal{X} denotes the set of probability distributions over X\mathcal{X}. It might be worth discussing [1], which also studies a similar IRL problem under regularization (given that they also highlight my first point geometrically).

A: Thank you for pointing out the missing definition and suggesting this related work. We have added the missing definition in the revised manuscript. Regarding the discussion with [1], [1] studies entropy-regularized IRL through reverse-KL occupancy matching and provides a geometric interpretation of reward updates in occupancy space. Its analysis offers a complementary perspective on the distinction between the expert occupancy and the regularized optimum. We have incorporated a discussion in the related works section.

[1] Diwan, A., Peters, J., and Arenz, O. “A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning.” NeurIPS, 2026.

[2] Zhao, H., Ye, C., Xiong, W., Gu, Q., and Zhang, T. “Logarithmic Regret for Online KL-Regularized Reinforcement Learning.” ICML, 2025.

[3] Li, S., Zhou, D., and Zhang, W. “Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning.” ICLR, 2026.

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

This paper studies adversarial imitation learning under finite-horizon, unknown transition dynamics, and general function approximation. The learner receives a fixed number N of expert trajectories and performs K rounds of online environment interaction. The authors focus on the question: can reward regularization and policy regularization, which are common in practice, simultaneously improve the finite-sample convergence rates in both the expert demonstration dimension and the online interaction dimension? The authors propose Dually Regularized AIL. Under conditions such as convexity of the reward class, Bellman completeness, and controlled complexity of the relevant function classes, Theorem 1 gives a high-probability cumulative regret bound; Corollary 1 further guarantees that the episode-level mixing of historical policies and the regularized saddle-point gap of the average reward are O~(1/K+1/N)\widetilde O(1/K+1/N). This paper is primarily a theoretical contribution and does not provide experimental validation.

Critical strengths

S1. The reward-side analysis tailored to the AIL sampling structure is valuable.

The authors set the OMD proximal term to a fraction of the cumulative empirical loss curvature, allowing the three-point inequality to be combined with the quadratic loss expansion: part of the curvature controls reward-update stability, while the remainder absorbs sampling errors. Lemmas 9–12 connect update stability to the generalized Eluder dimension of the reward class and align population variance with empirical curvature through a centered quadratic correction. The analysis accommodates a degenerate empirical reward seminorm without requiring a well-conditioned expert feature covariance. This combination of techniques, tailored to the AIL setting, is valuable. However, both the use of curvature to control optimization stability and the retention of negative quadratic terms to obtain statistical fast rates have established theoretical precedents. I therefore view this contribution as an analysis tailored to a particular sampling protocol and function class, rather than the introduction of a new curvature-cancellation principle. The precise technical advances over LS-IQ, strongly concave reward optimization in GAIL, and offset Rademacher complexity still need to be clarified, as discussed in W3.

S2. The treatment of adaptive reuse of fixed expert data is interesting.

In AIL, the reward iterates repeatedly depend on the same finite expert dataset, so the expert empirical error at each round cannot be treated as fresh, unbiased feedback. The paper first establishes a uniform concentration bound over pairs of reward functions and then applies it to the data-dependent reward iterates. This yields a cumulative expert-data contribution of approximately K/NK/N and a term of order 1/N1/N after averaging. The argument does not require a deterministic expert or fresh, independent demonstrations at every round, and therefore addresses a relevant data-reuse challenge in AIL.

Critical weaknesses

W1. The central sample-complexity comparison is not fair, and a fast-rate advantage under the same performance criterion has not been established.

The paper compares its O~(ϵ−1)\widetilde{O}(\epsilon^{-1}) sample requirement for achieving a fixed regularized saddle-point gap with the O~(ϵ−2)\widetilde{O}(\epsilon^{-2}) requirements for unregularized imitation performance. The former measures proximity to equilibrium in a modified game, whereas the latter measures the original expert–learner return gap; thus, the same ϵ\epsilon represents different performance requirements. This does not constitute a fair comparison under a common objective and accuracy level, nor does it establish improved sample efficiency for ordinary AIL. Although Table 1 and Remark 3 acknowledge this distinction, the paper lacks a comparison under a common performance metric that accounts for regularization bias, weakening the significance of its central fast-rate result for imitation learning.

This concern can be quantified. Let Gα,τG_{\alpha,\tau} denote the regularized saddle-point gap, let ΔR(π)=sup⁡r∈R[Vr(πE)−Vr(π)]\Delta_{\mathcal{R}}(\pi) = \sup_{r\in\mathcal{R}}[V_r(\pi^E)-V_r(\pi)], and let BEB_E denote the expert's expected cumulative KL divergence relative to the reference policy. Under the paper's ∣rh∣≤1|r_h|\le 1 convention and assuming finite expert KL divergence, a direct conversion yields

\le G_{\alpha,\tau}(\bar\pi,\bar r) +\frac{\alpha H}{2}+\tau B_E.$$ To obtain an overall bound of $O(\epsilon)$, one sufficient choice is $\alpha=\Theta(\epsilon/H)$ and $\tau=\Theta(\epsilon/B)$, where $B>0$ is an upper bound on $B_E$, together with an $O(\epsilon)$ regularized gap. However, Corollary 1 contains dependencies of $1/(\alpha\epsilon)$ and $1/(\tau\epsilon)$. Substituting these choices therefore yields sufficient expert-trajectory and online-episode sample requirements of order $\widetilde{O}(\epsilon^{-2})$, assuming fixed $H$ and $B$, controlled function-class complexity, and $\omega$ bounded away from its endpoints. It does not yield an $\widetilde{O}(\epsilon^{-1})$ guarantee for the original return gap. This is a general upper-bound conversion, rather than an exact characterization of the actual bias or a sample-complexity lower bound, and it does not rule out improvements under additional structural assumptions. Nevertheless, the stated theorem does not establish an advantage over prior work under the standard AIL performance criterion. The authors should provide a comparison under a common objective or clearly position their contribution as a statistical analysis of a regularized surrogate. A qualitative disclaimer alone does not resolve this central limitation. **W2. The general function-approximation guarantee lacks concrete instantiation and computational support.** The main theorem characterizes complexity through the covering numbers and generalized Eluder dimensions of the reward, value, and exploration bonus classes, and requires Bellman completeness under transformed rewards. The sample-size condition in Corollary 1 also depends implicitly on $(K,N)$ through these complexity measures. Therefore, boundedness of the functions or finiteness of the covering numbers alone is insufficient to directly establish a meaningful inverse-sample-size rate. The paper lacks a sufficiently developed tabular example or another tractable function-class example that simultaneously illustrates how the completeness condition, complexity growth, reference policy, and optimization subproblems satisfy the required assumptions. Moreover, the algorithm relies on exact least-squares solutions, OMD optimization over the reward class, and function-class disagreement measures. The computational feasibility of these operations and the effects of approximate optimization errors are not discussed. **W3. The technical distinctions from LS-IQ, strongly concave reward optimization in GAIL, and offset Rademacher complexity remain insufficiently clear.** First, LS-IQ already employs a quadratic reward penalty under an expert–learner mixture occupancy distribution and connects it to squared Bellman error, bounded $\chi^2$ divergence, and stability. Although the present paper cites LS-IQ, it should more clearly distinguish the inherited regularizer design from the new finite-sample analysis. Second, the analysis of GAIL with strongly concave reward objectives in *When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence* studies regularized GAIL under strong concavity in the reward parameters and also analyzes policy regularization. Thus, the use of reward regularization to provide useful curvature already has theoretical precedents within AIL. On the statistical side, offset Rademacher complexity employs a stochastic process with a negative quadratic offset to obtain localization and fast rates. This is closely related to the use of retained curvature to absorb sampling errors in the present proof. The authors should identify which parts of Lemmas 9–12 instantiate this existing mechanism and which require genuinely new arguments, rather than treating the absorption of stochastic fluctuations through quadratic curvature as a new principle in itself. These three lines of work do not exactly match the present setting: LS-IQ does not provide the same joint fast-rate guarantee for expert data and online interactions; the aforementioned analysis of GAIL with strongly concave reward objectives considers an algorithm that continuously collects batches of expert and learner samples, rather than analyzing the adaptive reuse of a fixed set of $N$ expert trajectories; and offset Rademacher complexity does not, by itself, provide a guarantee for this AIL sampling protocol. These precedents therefore do not directly invalidate Theorem 1. However, the authors should clarify, at the level of assumptions and proof mechanisms, what substantive extensions are required to address the degenerate occupancy-weighted seminorm, adaptive reuse of fixed expert data, changing online distributions, and Eluder-based stability control. This distinction is particularly important given that a fast-rate advantage for the original imitation error has not been established.
Questions for authors
  1. Does the sample-efficiency advantage survive evaluation under the same optimality gap criterion? Please quantify the regularization error and include it in the total accuracy requirement. Under the conversion above, shrinking α,τ\alpha,\tau with the target accuracy typically changes the sufficient sample requirements from Corollary 1 to O~(ϵ−2)\widetilde O(\epsilon^{-2}). Can the authors provide a tighter conversion or additional structure that preserves a better sample guarantee for the original return gap? Otherwise, Table 1 should clearly separate objectives that are not directly comparable and be supplemented with a comparison under the same original performance criterion, explaining which advantages over existing AIL results remain.

  2. What technical challenges does this paper address that are not addressed by these three lines of work? Please explicitly compare the paper with LS-IQ, the analysis of GAIL with strongly concave reward objectives in When Will Generative Adversarial Imitation Learning Algorithms Attain Global Convergence, and existing work on offset Rademacher complexity. Specifically: (1) Beyond the quadratic reward penalty under an expert–learner mixture already used in LS-IQ, what new reward-side results and proof techniques does the paper introduce? (2) Compared with the analysis of GAIL with strongly concave reward objectives, what additional challenges arise from adaptively reusing a fixed expert dataset and from the degeneracy of the empirical seminorm? (3) Can the retained-curvature/variance-cancellation argument in Lemma 12 be derived from existing localization techniques based on offset Rademacher complexity? If not, what substantive extensions are necessary? Please explain the differences in the underlying assumptions and key inequalities, rather than merely comparing the final convergence rates.

10 comments

Thank you for your valuable comments and suggestions. We provide our response to each question in turn below.

W1&Q1. Why using a regularized performance criterion instead of unregularized version?

Review Comments. The claimed sample-complexity improvement uses a regularized performance criterion, while the comparison includes ordinary imitation guarantees. The reviewer requests a quantitative treatment of regularization error and a comparison under a common criterion.

We would like to first clarify that the regularized performance criterion is well adopted in existing literautres for Multi-Armed Bandits, KL-regularized RL[1–2] and Markov Games [3-4]. In our work, the jointly regularized objective is motivated by existing AIL and RL methods. LS-IQ [7] studies a closely related quadratic reward penalty under an expert–learner mixture and connects it to a bounded Pearson χ2\chi^2 divergence and improved learning stability. Policy KL regularization expresses a preference for remaining close to a reference policy; a uniform reference recovers causal-entropy regularization. These motivations support studying the regularized objective directly, even though its optimizer can differ from the expert.

In addition, we would like to further clarify that seeking the same guarantee for unregularized imitation gap is infeasible: as established in [5, Theorem 3.2; formal Theorem G.1],for stochastic experts, the unregularized imitation gap has a worst-case Ω(ϵ−2)\Omega(\epsilon^{-2}) lower bound for expert complexity. [6] also establish an interaction complexity lower bound containing a ϵ−2exp⁡(−N)\epsilon^{-2}\exp(-N) term for unregularized AIL. Consequently, as stated in Remark 3, these rates do not directly imply the same sample complexity for the unregularized objective.

For prescribed α,τ>0\alpha,\tau>0, fixed ω∈(0,1)\omega\in(0,1), and controlled function-class complexity, our O~(1/K+1/N)\widetilde O(1/K+1/N) regularized dual-gap bound captures fast convergence in both expert demonstrations and online interactions, including stochastic experts and adaptive reuse of a fixed expert dataset. We will emphasize the distinction between performance criteria in the sample-complexity discussion and Table 1.

W2: Elaborate more on the sample complexity analysis for eluder dimension and computational support

Review Comments. The paper lacks a sufficiently developed tabular example or another tractable function-class example that simultaneously illustrates how the completeness condition, complexity growth, reference policy, and optimization subproblems satisfy the required assumptions.

We would like to note that the generalized Eluder dimension is widely used in the analysis of model-free RL literature with general function approximation [8, 9]. It admits explicit bounds under various cases including linear function approximation [8].

Our algorithm could also be applied into a special case like linear function approximation. Here we provide the construction, verifying completeness, complexity growth, the reference policy, and the optimization subproblems together.

For the completeness condition and reference policy. Consider linear function approximation with known base features φ(s,a):S×A↦Rp\varphi(s,a):\cal S\times A\mapsto\Bbb R^p with ∥φ(s,a)∥2≤1\|\varphi(s,a)\|_2\le1. Assume that

\qquad P_h(s'\mid s,a)=\varphi(s,a)^\top d\mu_h(s'),$$ where $\mu_h$ is unknown and defines a valid transition kernel. Let $\|\theta_h\|_2\le 1$ and $\|\int V(s')d\mu_h(s')\|_2\le\sqrt p \|V\|_\infty$. For the shaped reward $u_{r,h}=r_h+\frac{\alpha(1-\omega)}2 r_h^2$, define the lifted feature map $$\phi(s,a)=\frac1{\sqrt2} \begin{pmatrix} \varphi(s,a)\\ \operatorname{vec}(\varphi(s,a)\varphi(s,a)^\top) \end{pmatrix}\in\mathbb R^d.$$ Here $\operatorname{vec}$ preserves the Frobenius inner product, so $\|\phi_h(s,a)\|_2\le1$. The dimension $d=p+p^2$ refers to the lifted feature vector. Rewards are still linear in these features, with coefficient vector $\sqrt2(\theta_h,0)$. For any value function $V$ satisfying $\|V\|_{\infty}\le V_{\max}$, let $$w=\sqrt2\left(\theta_h+\int V(s')\mu_h(ds'), \frac{\alpha(1-\omega)}2\operatorname{vec}(\theta_h\theta_h^\top)\right)$$ we then have $(u_{r,h}+P_hV)(s,a)=\langle w,\phi(s,a)\rangle$. Since $|r_h(s,a)|\le1$ and $V_{\max}=H(1+\alpha(1-\omega)/2)$, $$\|u_{r,h}+P_hV\|_\infty \le 1+\frac{\alpha(1-\omega)}2+V_{\max} \le 2V_{\max}.$$ Together with the linear representation above, this verifies Bellman completeness for $$\mathcal F_h=\left\\{w^\top\phi:w\in\mathbb R^d,\ |w^\top\phi(s,a)|\le2V_{\max}\text{ for all }(s,a)\right\\}.$$ Finally, choose the uniform reference policy $\pi_h^{\mathrm{ref}}(a\mid s)=1/|\mathcal A|$. Every expert, including a stochastic expert, then has finite expected cumulative KL cost, bounded by $H\log|\mathcal A|$.

For the complexity growth. To make the statistical guarantee explicit, use the common augmented feature dimension dd defined above. Assume a suitable fixed ω∈(0,1)\omega\in(0,1), e.g. 1/21/2, and small enough α\alpha. Factors involving ω\omega, 1−ω1-\omega, and 1+α1+\alpha can then be absorbed into constants, while the dependence on α−1\alpha^{-1} remains explicit.

For the reward class, the generalized Eluder dimension in Theorem 1 satisfies

\le2d\log\left(1+\frac{2K^3}{d}\right) =\widetilde O(d).$$ For the regression class, the linear potential argument gives $$\dim_K(\mathcal F,\lambda) \le 2d\log\left(1+\frac{16V_{\max}^2K}{\lambda}\right).$$ In particular, $\lambda=1$ yields $\dim_K(\mathcal F,1)=\widetilde O(d)$. For the covering number, we also have $$\log\mathcal N_{\mathcal R_h}(\kappa) \le d\log\left(1+\frac2\kappa\right), \qquad \log\mathcal N_{\mathcal F_h}(\kappa) \le d\log\left(1+\frac{4V_{\max}}\kappa\right).$$ Thus the covering scales $1/K^2$ and $1/N^2$ introduce only logarithmic sample-size dependence. The exploration bonus depends on the history through a Gram matrix. For $\lambda>0$, the exact quantity $D_{\mathcal F_h}$ is Lipschitz in this matrix. A matrix covering argument consequently gives $$\log\mathcal N_{\mathcal B_h}(\kappa) =\widetilde O(d^2)$$ at the covering scales used in Theorem 1. Consequently, direct substitution into Theorem 1 and Corollary 1 gives, with probability at least $1-\delta$, $$\operatorname{Gap}(\bar\pi_K,\bar r_K) \le \widetilde O\left( \frac{Hd}{\alpha} \left(\frac1K+\frac1N\right) + \frac{H^5d^3}{\tau K} \right).$$ Here $\operatorname{Gap}$ is the regularized imitation gap, and the suppressed factors are logarithmic in the sample sizes, confidence level, and bounded class parameters. The expert and interaction sample complexities are therefore $$K = \widetilde O\left( \frac{Hd}{\alpha\epsilon} + \frac{H^5d^3}{\tau\epsilon} \right), \qquad N = \widetilde O\left( \frac{Hd}{\alpha\epsilon} \right).$$ This resolves the implicit dependence on $K,N$: for these classes, the complexities grow only logarithmically with the sample sizes. For the tabular instance, take one-hot features with $d=|\mathcal S||\mathcal A|$, $\mathcal R_h=[-1,1]^d$, and $\mathcal F_h=[-2V_{\max},2V_{\max}]^d$. Squaring a reward stays in the same span, so augmentation is unnecessary. Bonuses depend only on the $d$ visit counts, giving $\log\mathcal N_{\mathcal B_h}(\kappa)\le d\log(K+1)$. The same displays therefore hold with $d^3$ replaced by $d^2$ in the planning term. **Computational complexity of the optimization.** In this finite-domain linear instance, the optimization problems have explicit convex formulations. The regression problem in Eq. (3) is constrained least squares over $w$, subject to the bounded-output constraints defining $\mathcal F_h$. Computing $D_{\mathcal F_h}$ from Definition 1 admits a second-order cone formulation using these same constraints. The OMD step in Eq. (6) is a convex quadratic optimization problem over the reward coefficients. Redundant coefficient directions can be removed without changing the represented functions. We will update a dedicated section to the Appendix for the special case of linear function approximation. > **Review Comments.** Moreover, the algorithm relies on exact least-squares solutions, OMD optimization over the reward class, and function-class disagreement measures. The computational feasibility of these operations and the effects of approximate optimization errors are not discussed. We would like first to point out that the exact solution assumptions are widely applied in the RL with general function approximations. Zhao et al. [2, Algorithms 1–2] use exact regression and exploration bonuses. VOQL [8] specifies regression and bonus oracles, while Huang et al. [10, Section 4.2] assume a weighted regression oracle. Extending the stated guarantee to inexact solutions requires a separate error analysis and should be considered the future work. Besides the poilcy-side optimization subproblems, we would also like to give a brief describtion on the computational cost of the reward upadte. In particular, for a general convex reward class, the OMD proximal objective \$\langle\widehat g_k,r\rangle +\tfrac12 {\alpha\rho} \sum_{h=1}^H\|{r_h-r_{k,h}}\|_{k,h}^2\$ is convex in the reward function $r$, though efficient computation still requires a tractable representation of the class. We will explicitly state the computational assumptions for least-squares regression, OMD reward updates, and exploration bonus computation.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revision Summary

Dear Reviewers and Area Chair,

We sincerely thank you for your time and effort in reviewing our manuscript and for your valuable feedback. We have revised the manuscript to incorporate your suggestions and address the concerns raised during the review process. The key revisions are highlighted in red in the updated manuscript and summarized below:

  • Related Work: We have added a discussion of Diwan et al. (2026), highlighting the geometric interpretation of reward updates and the relationship between expert occupancy and the regularized optimum.

  • Clarifications in Preliminaries: We have defined ΔX\Delta_{\mathcal{X}} as the set of probability distributions over X\mathcal{X} and explicitly stated the requirement that the expert have finite expected cumulative KL cost relative to πref\pi^{\mathrm{ref}}, including the corresponding support condition.

  • Computational Justifications: We have clarified the oracle assumptions for least-squares regression, OMD reward updates, and exploration-bonus computation in Section 4.

  • Linear Function Approximation: We have added a specialization to linear MDPs in Appendix E, including verification of the required assumptions, explicit sample-complexity guarantees, and concrete optimization formulations for the algorithm’s subproblems.

  • Connection to Unregularized Imitation Learning: We have added a bound relating the regularized dual gap to the unregularized imitation gap in Appendix F and discussed the tradeoff between faster convergence and regularization bias. We have also clarified the distinction between the performance criteria compared in Table 1.

  • Empirical Evaluation: We have added tabular MDP experiments in Appendix G, including log–log plots examining sample scaling with online interactions KK and expert demonstrations NN, comparisons with unregularized AIL and projected-gradient reward updates, and ablations examining how α\alpha and τ\tau affect convergence and the distance to the expert.

We appreciate your constructive feedback, which has helped us improve the clarity and completeness of our manuscript.

Best regards,

The Authors

Dear Reviewers and Area Chair,

We sincerely thank you for your constructive feedback and valuable suggestions. We have provided detailed responses, additional theoretical analyses, new experiments, and substantial manuscript revisions to address the concerns raised. We briefly summarize the key updates below:

  1. Regularized guarantees and imitation performance. We clarified the distinction between regularized and unregularized imitation objectives and established an explicit bound connecting the regularized dual gap to the unregularized imitation gap. We further discussed the tradeoff between faster convergence and regularization bias in Appendix F.

  2. Theoretical novelty and analysis. We clarified our contributions beyond existing AIL methods, particularly the occupancy-weighted OMD reward updates, retained-curvature analysis, and generalized Eluder-dimension guarantees. These techniques establish O~(1/K+1/N)\widetilde{O}(1/K+1/N) convergence for the regularized objective while reusing a fixed expert dataset.

  3. Concrete instantiation and computational feasibility. We added a specialization to linear MDPs in Appendix E, verifying the required assumptions, deriving explicit sample-complexity bounds, and providing concrete optimization formulations. We also clarified the computational oracle assumptions.

  4. Additional experimental validation. We introduced tabular MDP experiments across 20 random seeds, validating convergence scaling with online interactions and expert demonstrations. We further compared against unregularized AIL and conducted ablations on the regularization parameters α\alpha and τ\tau, as detailed in Appendix G.

  5. Manuscript improvements. We expanded the related work discussion, clarified the reference-policy support assumptions and notation, and improved the presentation of our theoretical guarantees and their limitations.

We believe these additional analyses, experiments, and revisions substantially address the reviewers' principal concerns and strengthen the theoretical and empirical contributions of our work.

As the discussion period approaches its end, we would greatly appreciate it if the reviewers could revisit our detailed responses and revised manuscript and indicate whether their concerns have been adequately addressed or if any outstanding questions remain.

Thank you again for your time, consideration, and constructive feedback.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.