{"id":"abb733e2-5d36-4015-bddf-c6d58150d8ec","arxiv_id":"2607.29617","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Interactive imitation learning works with only expert-value realizability, while offline learning under the same assumption is provably hard.","lead":"This paper shows that if an imitation-learning agent can query an expert along its own paths, it only needs to model the expert's value function, not the expert's full policy, to match the expert's return. This reframes when online interaction helps and shows offline methods cannot exploit the weaker representation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest assumption—the interactive on-policy query protocol—is indeed a necessary condition for the central claim, and Theorem 4.1 shows that without it Q^πE-realizability is insufficient. This is a real boundary on the claim's applicability, but the paper's title and framing make this the intended setting, and the proof of Theorem 3.1 appears internally sound. I could not identify a hidden assumption of policy realizability, reward observability, or closure of Q under learner policies. The remaining issues that motivated the reader's CONDITIONAL verdict—the unproven chain-of-thought sketch and missing error bars in the empirical figures—are legitimate but do not undermine the central reduction. Therefore no change to the reader's verdict is needed.","tokens_in":61387,"tokens_out":42647,"duration_ms":398913,"concrete_test":"Independently re-derive Lemma F.1 and Theorem F.1 from first principles, checking that (i) the Q-player's argmax over Q_h is the only use of Q, (ii) the per-state regret bound does not require π_E∈Π, and (iii) the uniform-concentration bound covers all reachable π^k without completeness assumptions. Also run Algorithm 1 (not the stationary approximation) on the synthetic hard family from Theorem 4.1 to confirm the predicted query complexity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that interactive value-based IL is feasible under Q^πE-realizability alone—is supported by a coherent reduction (Theorem 3.1 and Appendix F). The proof uses only Q^πE-realizability: the performance-difference decomposition, the Q-player best response over Q_h, the no-regret policy update, and a uniform-concentration argument whose complexity is log|Q|, never the learner's policy class. The offline lower bound (Theorem 4.1) is consistent and shows the interactive query protocol is genuinely load-bearing; but the paper explicitly frames this as the setting and proves necessity, so it is a scope condition rather than an internal inconsistency. I could not locate a step where the argument silently assumes policy realizability or reward observability.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies value-based imitation learning in episodic MDPs, comparing offline access to expert trajectories with interactive access in which the learner rolls out its own policy and queries the expert for actions on the resulting states without observing rewards. The central claim is that interactive on-policy expert queries relax the representational requirement from policy realizability to only Q^{πE}-realizability. The authors introduce OVI, a layerwise no-regret algorithm in which a Q-player best responds over a value class Q while a policy player performs exponentiated-gradient updates. Theorem 3.1 gives an ε-suboptimality guarantee using eO(H^5 Qmax^4 log(A) log(|Q|/δ)/ε^4) expert queries, with the complexity controlled by log|Q| rather than by a learner policy class. Theorems 4.1 and 4.2 show that offline IL cannot achieve this: any offline algorithm needs Ω(|X|/ε) samples even with |Q|=2, and a broad class of value-induced offline algorithms fails even with infinite data. Theorem 3.2 shows reward realizability alone is insufficient even with interaction. The paper also gives representational-separation examples, Gym experiments, and a discussion of implications for chain-of-thought learning.","tokens_in":61436,"tokens_out":33811,"duration_ms":342102,"significance":"If the results hold, they settle a natural and previously open question: interaction in value-based IL buys representational relief, not only improved horizon dependence. The main upper bound is a genuine derivation — performance-difference decomposition, sup-Q relaxation, no-regret exponential weights, and uniform concentration over Q — and the complexity term log|Q| is not contaminated by an arbitrary policy class. The matching offline lower bound with |Q|=2 shows that the interactive query protocol is genuinely load-bearing rather than a technical convenience. The paper also provides a reward-realizability lower bound, separation examples showing Q^{πE}-realizability can be much weaker than policy realizability, and code for reproducible experiments. I did not find a circular step: Q^{πE}-realizability is an external representational assumption, and the proof does not quietly introduce policy realizability or reward observability. The scope conditions are stated honestly: the positive result requires the learner to query the expert on its own state distribution, and the CoT application requires the stronger token-level value-realizability.","major_comments":[],"minor_comments":[{"comment":"The sentence 'the total number of learner interactions with the environment obeys the same bound with an extra factor of H' is easy to misread. To sample n_E states at layer h, OVI must roll out h−1 steps for each sample, so environment transitions scale as Θ(H^2 n_E/2) rather than H·(expert queries) in a literal accounting. The eO order is unchanged up to constants, but the resource accounting should be stated precisely.","section":"Section 3.1 (paragraph after Theorem 3.1)"},{"comment":"The claimed 'exponential computational improvement' over Joshi et al. (2026) is argued informally: global search over Σ^H is replaced by H token-level softmax updates. Since this is listed as a contribution, please state the computational model (oracle calls, access to Q, what is counted) and what exactly is exponential, or explicitly mark the discussion as suggestive rather than a formal theorem.","section":"Section 5"},{"comment":"The phrase 'algorithm with a VI policy class' should be aligned with Definition 4.2, which defines 'uses a value-induced policy class.' Also, clarify whether the pointwise-limit convention is part of the output-policy class available to the algorithm or only a device for including greedy policies in the lower-bound statement.","section":"Definition 4.2 / Theorem 4.2"},{"comment":"The claim that layer-wise updates introduce 'memory requirements that scale linearly with the horizon' is incomplete: outputting πout,h=(1/K)Σ_k π^k_h requires storing K Q-functions per layer, so memory also scales with K=O(H^2 Qmax^2 log A / ε^2). This is presumably intended, but the wording omits the 1/ε^2 dependence.","section":"Algorithm 1 and Section 3.1"},{"comment":"The experiments use a stationary approximation of OVI (Algorithm 2), while the theorem and proofs analyze nonstationary Algorithm 1. The text does acknowledge this, but the figure caption and the phrase 'OVI outperforms' would benefit from an explicit pointer that the plotted method is the stationary approximation.","section":"Figure 1 / Section 3.3"}],"recommendation":"minor_revision","confidential_remarks":"For the editor: in my reading the core proof is sound and the lower bounds make the interactive-protocol assumption load-bearing rather than a hidden weakness. The main reservation is the informal computational claim in Section 5; if the authors either formalize it or soften the wording, I would be comfortable moving toward acceptance. I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, the main theorem is real. OVI is the first algorithm I know of that is provably efficient under Q^πE-realizability alone, with a sample complexity that depends on log|Q| rather than on the learner's policy class. The proof is a clean reduction: performance difference lemma, a saddle-point formulation, no-regret updates for the policy player, and uniform concentration over Q. I checked the key steps in the appendix and did not find a place where policy realizability or reward observability is silently assumed. The offline lower bound with |Q|=2 is a genuinely separate result and it shows the interaction protocol is load-bearing, not decorative. The reward-realizability lower bound for H=2 is a nice extension of the bandit result. This is a serious theoretical contribution.\n\nSecond, the paper's soft spots are real but not fatal. The chain-of-thought section claims an exponential computational improvement, but as written it is an argument sketch, not a theorem. The paper should either formalize it or explicitly label it as a conjecture. The Gym experiments support the qualitative story but lack error bars and variance reporting; for a paper whose headline is about representational tradeoffs, the empirical curves need more than 50 seeds averaged without spread. Minor: the code URL is provided but there is no commit hash, so reproducibility is good but not excellent. The ε−4 rate in Theorem 3.1 is worse than policy-based methods, but the authors acknowledge this and it is not a hidden flaw.\n\nI disagree with neither the reader's conditional verdict nor the stress-test note. The central claim is likely correct, and the scope condition—interactive on-policy expert queries—is exactly what the lower bound says is necessary. If you only have a fixed offline dataset, the central claim does not apply, but the paper never claims it does.\n\nWho is this for? Anyone working on imitation learning theory, especially on the value-based side, or on distillation with a capacity gap. It deserves a serious referee. I would not desk-reject it. The main things to ask for in revision: formalize or conjecture-ify Section 5, add error bars, and maybe include a simple pseudocode for the stationary approximation in the main text.","headline":"OVI's interactive value-based IL under expert-value realizability is a genuine new result with a sound proof; the chain-of-thought section and empirical reporting are the weak spots, not the core theory.","tokens_in":62034,"tokens_out":1245,"would_cite":true,"duration_ms":17824,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that interactive imitation learning requires only the expert's value function, not the expert's policy.","keywords":["imitation learning","value-based imitation learning","on-policy interaction","Q-function realizability","policy realizability","sample complexity","offline imitation learning","chain-of-thought learning"],"falsifier":"Run the OVI protocol on a finite MDP family with |Q|=2 satisfying Q^piE-realizability but where no small policy class realizes the expert; if any offline algorithm, given only expert trajectories and no interaction, achieves epsilon-suboptimality with o(|X|/epsilon) samples, Theorem 4.1 is false. An experimental shortcut is to repeat the paper's width-sweep experiments: if shrinking the learner network fails to produce a growing performance gap favoring the interactive value-based method over behavior cloning and DAgger, the representational mechanism is not being observed.","tokens_in":61179,"feed_emoji":"🤖","tokens_out":5318,"duration_ms":59905,"temperature":0.7,"pith_summary":"This paper asks when on-policy interaction actually helps in imitation learning. Its central claim is that interaction combined with value-based learning relaxes what the learner must represent: instead of a model that can output the expert's policy, the learner only needs a model that can represent the expert's value function. The paper introduces OVI, an algorithm that queries the expert along the learner's own trajectories and provably attains epsilon-optimal return with sample complexity governed by the value-function class alone. A matching negative result shows that without such interaction, value-function realizability alone is not enough: any offline imitation algorithm must scale with the number of states or the complexity of the expert policy class. These findings reframe the benefit of interactive imitation and explain why smaller learner networks can succeed by matching values rather than actions.","feed_headline":"To imitate well, query the expert, not model its policy","feed_subtitle":"Interactive value-based imitation matches expert returns with a smaller learner by needing only the expert's value function.","key_machinery":"The carrying mechanism is the performance-difference-lemma decomposition of the imitation gap into stage-wise advantage terms, combined with the assumption Q^piE in Q. OVI converts this decomposition into a min-max saddle-point game between a policy player, updated by exponentiated-gradient softmax mirror ascent, and a value-function player that best-responds over Q at each layer h. The layer-wise order is load-bearing: the state sampling distribution at layer h depends only on previously fixed layers, so the learner can estimate the objective on-policy before optimizing the current decision rule. This isolates the statistical capacity of Q, rather than the policy class, as the driver of sam","core_discovery":"On the paper's own terms, the discovery is that the interaction protocol changes which representational assumption is sufficient. Under Q-pi-E-realizability—the requirement that the learner's value-function class contain the expert's Q-function—the OVI algorithm matches the expert's return to epsilon precision using expert queries that scale polynomially with horizon and accuracy and only logarithmically with the size of the value class. No assumption is placed on the learner's policy class. OVI turns the performance-difference lemma into a layer-wise min-max game: at each layer it samples states from its own current state distribution, queries expert actions there, and runs softmax mirror-a","pith_inferences":["Testable in practice: in language-model distillation, querying the teacher on student-generated tokens with a value-based objective should outperform behavior-cloning of teacher tokens when the student is much smaller; the paper's theory predicts the gap grows with expressivity mismatch.","The offline lower bound is circumvented if expert trajectories provide good state coverage, which suggests practical offline imitation should focus on coverage guarantees rather than only enlarging the value class.","The value-versus-policy realizability separation implies that imitation systems should learn value-relevant features and ignore action tie-breaking or exogenous details, so a robotics or driving learner may not need to model arbitrary human choices that do not affect outcomes.","The paper notes that its chain-of-thought gains are theoretical; whether they translate to LLM distillation is an open empirical question, making value-based on-policy distillation a natural next benchmark."],"forward_implications":["A student that cannot faithfully reproduce the expert's action distribution can still match the expert's return if it can represent the expert's value function.","Expert-query complexity scales with the statistical capacity of the value-function class, not the expert policy class, so less expressive learner networks are not inherently doomed in imitation.","Offline imitation under Q^piE-realizability is information-theoretically hard: without interaction or an added coverage condition, any algorithm must pay Omega(|X|/epsilon) samples.","Reward realizability is insufficient even with interaction; the learner also needs transition-dependent information that the expert Q-function encodes.","In chain-of-thought learning, value-based interaction decomposes the intractable search over complete responses into token-level updates, offering an exponential computational improvement over sequence-level reward approaches."],"fun_headline_variants":["Query expert, not policy, for efficient imitation","Value-based imitation with queries beats policy cloning","Expert interaction lifts representational limits in imitation","Imitation: needing only value function, not policy, with queries"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the learner can repeatedly roll out in the same unknown MDP and query the expert for actions at the states it visits, without observing rewards; if only a fixed dataset of expert demonstrations is available, the paper's main positive claim does not apply.","fun_headline_variants_meta":{"raw":{"variants":["Query expert, not policy, for efficient imitation","Value-based imitation with queries beats policy cloning","Expert interaction lifts representational limits in imitation","Imitation: needing only value function, not policy, with queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000262,"raw_usage":{"total_tokens":1461,"prompt_tokens":802,"completion_tokens":659,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":598}},"tokens_in":546,"tokens_out":659,"duration_ms":7359,"temperature":1.0,"reasoning_tokens":598,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T03:24:35.792611+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the OVI protocol on a finite MDP family with |Q|=2 satisfying Q^piE-realizability but where no small policy class realizes the expert; if any offline algorithm, given only expert trajectories and no interaction, achieves epsilon-suboptimality with o(|X|/epsilon) samples, Theorem 4.1 is false. An experimental shortcut is to repeat the paper's width-sweep experiments: if shrinking the learner network fails to produce a growing performance gap favoring the interactive value-based method over behavior cloning and DAgger, the representational mechanism is not being observed.","supporting_citations":[],"review_version":1}