Offline imitation learning in $Q^\pi$-realizable MDPs without expert realizability

Thank you for your encouraging review and your careful reading of our paper! Please find our answers below.

1. 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.
2. 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.
3. Yes, it is the Euclidean norm; we will define it explicitly.
4. 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.
5. Thank you for spotting these! We will fix them.
6. This is a good point; we will explain more carefully what we mean by trajectory access.

Thank you again for your valuable feedback. We are happy to discuss further if you have any other questions.

References

[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.

[2] Mhammedi, Z.. (2025). Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions. Thirty Eighth Conference on Learning Theory.

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.

Before 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.

Answers to the points raised in "Weaknesses"

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.

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.

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. While 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. Our 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$.

4. Regarding the intuition. Thanks for the suggestion! We will add some additional intuitive explanations.

Answers to the questions

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.

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).

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.

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.

We 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.

References

[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.

[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.

[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.

Thank you for your positive review, encouraging words, and insightful feedback! We answer the points you raised below.

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).

Moreover, 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).

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.

The 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.

Comparison with inverse reinforcement learning: Inverse Q-learning methods, such as SPOIL, have distinct trade-offs with inverse reinforcement learning (IRL).

• 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.
• 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.

Thanks again for your feedback. We are available for any further questions.

References

[3] Ziebart, B. D. (2010). Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University. Section 6.2.

[4] Syed, U., and Schapire, R. E. (2007). A game-theoretic approach to apprenticeship learning. Advances in neural information processing systems, 20.

Dear Reviewer,

Thanks a lot for your answer and for your support.

The continuous action extension is indeed very interesting, we will think about it. Thank you for your helpful comments about this setting.

Best, Authors

Thank you for reviewing our work and for your positive evaluation. We are happy to address your questions below.

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.

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.

To 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.

Thank you again for your feedback. We are happy to discuss further if needed.