{"id":"5456284d-4ac9-40e4-a99a-531d0dc6aec7","arxiv_id":"2602.22810","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"In linear Markov games, behavior cloning's sample complexity hinges on a feature-level concentrability coefficient, and the interactive algorithm LSVI-UCB-ZERO-BC removes concentrability dependence entirely, scaling only with feature dimension d.","lead":"This paper gives the first sample-complexity analysis of imitation learning in multi-agent games with linear feature structure, and builds an interactive algorithm whose guarantee depends only on the feature dimension. A deep-learning version of the interactive scheme beats plain behavior cloning at Tic-Tac-Toe and Connect4.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.4 rests on an unproven extension of LSVI-UCB regret to quadratic, time-varying exploratory rewards; if that extension fails, the dimension-only interactive sample complexity collapses.","rationale":"The reader's weakest assumption and my analysis coincide: Lemma 4.4 is the load-bearing step of Theorem 4.1. The entire interactive sample-complexity claim depends on the unproven extension of LSVI-UCB regret to non-linear, time-varying exploration rewards. This is not a minor technicality—quadratic rewards break linear Bellman completeness, which is exactly the property LSVI-UCB relies on. The paper's own appendix acknowledges the need for a 'minimal variation' but supplies no argument. Without this lemma, the algorithm's coverage guarantee is unsupported, and the main contribution of the paper is not established. I therefore recommend CONDITIONAL: the paper should be accepted only if the authors provide a correct proof of Lemma 4.4 (or a correct alternative), and if that proof is supplied the central claim would be substantially validated. The secondary concerns (C_φ,max ≤ C_max not proven, Assumption 3.1 scope) are real but less severe: they qualify the non-interactive result, whereas Lemma 4.4 is the crux of the interactive result, which is the paper's headline novelty. My verdict matches the reader's conditional verdict; the concern would move a naïve accept to conditional, but since the reader already set conditional, no further adjustment is needed beyond insisting on the missing proof in revision.","tokens_in":50293,"tokens_out":7834,"duration_ms":82142,"concrete_test":"Write out a self-contained proof of Lemma 4.4 without citing Viano et al. 'up to minimal variation.' Specifically, analyze the Bellman recursion for the quadratic exploration reward r_h^k(x,a)=||φ(x,a)||_{(Λ_h^k)^{-1}}: check whether the optimal Q-function (or the LSVI-UCB estimate) remains of the form φ^⊤θ + bonus. If it does not, the O(H^2 d^{3/2}B√(Klog)) regret bound does not follow. Equivalently, construct a small linear MDP (e.g., d=2, H=2) where the expert policy is fixed, simulate Algorithm 2 for increasing K, and measure max_{π} Σ_h ||φ^{π,π^E}||_{(Λ_h^K)^{-1}}; if it does not decay as K^{-1/2}, the lemma is false. Either outcome settles the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The interactive guarantee (Theorem 4.1) hinges on Lemma 4.4, which asserts that the feature-level coverage term max_{π^{-n}} ||φ^{π_n^E,π^{-n}}||_{(Λ^{-n,K})^{-1}} decays as O(√(d^3H^4B^2ι/K)). The proof in Appendix E.2 invokes Viano et al. [2024, Thm 6] 'up to a minimal variation to accommodate quadratic rewards instead of linear ones.' This is not a proof. The exploratory reward r_h^k(x,a)=||φ(x,a)||_{(Λ^{k,h})^{-1}} is quadratic in φ, not linear. The Q-functions of a policy under this reward are therefore not in the linear span of φ, so the standard LSVI-UCB regret analysis—which requires r_h(x,a)=φ(x,a)^⊤θ_h—does not apply. Moreover, Algorithm 2 does not actually run LSVI-UCB on this quadratic reward; it runs zero-reward LSVI-UCB with a bonus (β+1)||φ||_{Λ^{-1}}. The cited regret theorem concerns a different objective. If Lemma 4.4 fails, the central claim that interactive MAIL in linear Markov games has sample complexity independent of the state space and concentrability has no support. The proof also uses the decreasing property r^{k+1}≤r^k to replace a sum by K times the final reward, which is delicate when the reward itself is data-dependent; this step is not justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-agent imitation learning (MAIL) in linear Markov games. In the non-interactive setting, it replaces the tabular all-policy-deviation concentrability coefficient C_max with a feature-level coefficient C_{φ,max} and proves a behavior-cloning sample-complexity bound scaling with C_{φ,max} (Theorem 3.3). In the interactive setting, it proposes LSVI-UCB-ZERO-BC, combining a synthetic quadratic exploratory reward with zero-reward LSVI-UCB and behavior cloning, and claims a sample complexity depending only on the feature dimension d and not on the state space (Theorem 4.1). An infinite-horizon extension is sketched with RMAX-RAVI-LSVI-UCB (Appendix G), and a deep heuristic DQN-Explore-BC is evaluated on Tic-Tac-Toe and Connect4. The core technical pivot is the feature-level change of measure (Lemma D.6) and the assertion that the exploratory covariance matrix contracts uniformly over policy deviations (Lemma 4.4).","tokens_in":50641,"tokens_out":2232,"duration_ms":25387,"significance":"If correct, the paper makes three substantive contributions. First, it identifies a feature-level concentrability coefficient C_{φ,max} that can be finite when the tabular C_max is unbounded, and it provides a clean, parameter-free non-interactive BC bound in terms of this coefficient. Second, it proposes an interactive MAIL algorithm whose stated complexity is independent of both the state space and any concentrability coefficient — a qualitative advance over tabular MAIL. Third, it connects the linear-theory exploration scheme to a practical deep algorithm backed by experiments in two solved games. The non-interactive analysis (Lemma D.6 and Theorem D.5) is self-contained and, conditional on Assumption 3.1, appears sound. However, the central interactive guarantee rests on an unproven extension of a regret bound to quadratic exploratory rewards; without that extension the headline Theorem 4.1 is unsupported. The paper also explicitly acknowledges that Assumption 3.1 excludes some Nash equilibria, limiting the non-interactive claim.","major_comments":[{"comment":"The proof of Lemma 4.4 invokes Viano et al. [2024, Thm 6] 'up to a minimal variation to accommodate quadratic rewards instead of linear ones.' This is load-bearing but not demonstrated. The exploratory reward r^{k,h}(x,a)=||φ(x,a)||_{(Λ^{k,h})^{-1}} is quadratic in φ, not linear, so the Q-functions of a policy under this reward are not in the linear span of φ; the cited regret theorem requires r_h(x,a)=φ(x,a)^T θ_h. Moreover, Algorithm 2 does not run LSVI-UCB with the quadratic reward as the actual reward; it runs zero-reward LSVI-UCB with a bonus (β+1)||φ||_{Λ^{-1}}. Showing these two formalisms are equivalent, or otherwise proving the required regret bound for the actual algorithm, is essential. The statement 'up to a minimal variation' is not a proof. If this extension fails, the dimension-only interactive sample complexity collapses.","section":"Appendix E.2, Lemma 4.4"},{"comment":"The step after the regret bound uses the property r^{k+1} ≤ r^k to replace a sum over k by K times the final reward. The reward itself is data-dependent: r^{k+1} is defined through Λ^{k+1}, which is built from previous random transitions. The monotonicity Λ^{k+1} ⪰ Λ^k implies the pointwise inequality of norms for fixed (x,a), but the execution also changes the data distribution; the proof does not justify why the final-reward summand can be upper bounded by the sum of the per-episode expectations. This step is delicate and needs a rigorous treatment.","section":"Lemma 4.4 proof, decreasing-reward step"},{"comment":"The non-interactive Theorem 3.3 is conditional on Assumption 3.1, which requires the expert Nash equilibrium to be a limit point of the softmax-linear class. The paper itself (Appendix D, discussion after Lemma D.4) gives a normal-form matrix for which only the uniform policy is recoverable, and concludes that some Nash equilibria violate the assumption. This is an acknowledged limitation, but it means the sentence in the abstract that BC 'replaces' the state-action coefficient with C_{φ,max} should be read as holding only for a subclass of equilibria. The claim is not false, but the scope is narrower than the main-text presentation suggests.","section":"Assumption 3.1 and Appendix D"},{"comment":"The infinite-horizon extension repeats the same pattern as the finite-horizon proof: RMAX-RAVI-LSVI-UCB is said to tolerate only 'slow-changing' bonuses and the proof is deferred to an analogy with the bonus sequence in Moulin et al. [2025b]. The paper itself notes that RMAX-RAVI-LSVI-UCB 'can not naively tolerate quadratic reward,' but the proposed slow-changing reward fix is described only at a high level. Lemma G.1's regret bound against the quadratic reward function is therefore also unsupported by the cited theorem.","section":"Appendix G, Lemma G.1"}],"minor_comments":[{"comment":"Two feature maps φ^1 and φ^2 are defined but the text then says 'without loss of generality we assume that the features vector are independent of the player index' and uses a single φ. This should be stated earlier and more rigorously; the WLOG claim needs a short justification.","section":"Section 2.1, Assumption 2.1"},{"comment":"Typo: 'informative aboutstates’ similarity' should be split; also the phrase 'potentially much smaller than' is not a formal statement. The comparison C_{φ,max} ≤ C_{max} is asserted without a proof location; a pointer to a lemma would help.","section":"Abstract and Section 1"},{"comment":"The pseudocode initializes Λ_{−n,h}^0 = I and then defines Λ_{−n,h}^k = Λ_{−n,h}^{k−1} + φ φ^T, while Lemma 4.3 states Λ^{−n,K}_h = Σ_k φ φ^T + I. These are consistent, but the 'Return' dataset is written as D^n = {X^{−n,k}_h, A^{n,k}_{E,h}}; the expert action variable A^{n,k}_{E,h} is not explicitly defined in the pseudocode before the loop. Clarify indexing.","section":"Algorithm 2"},{"comment":"The deep algorithm is essential for the empirical claims but its pseudocode is informal: 'approximately solve' is not specified, and the interplay between target network, OldInitialLayers, and the exploratory reward is under-specified. Since this is an heuristic extension, a precise description is needed for reproducibility.","section":"Appendix H, Algorithm 5"},{"comment":"The proof uses a Chernoff bound and Ville's inequality; the derivation of the supermartingale inequality exp(x) ≤ 1+x+x^2 for x≤1 is only valid for x bounded above, but the martingale argument requires the exponential of the sum to be integrable. This is standard but should be stated as a condition or handled with truncation.","section":"Lemma J.4"}],"recommendation":"major_revision","confidential_remarks":"The paper's non-interactive contribution is likely publishable after minor cleanup, but the interactive result — the headline of the paper — is not yet proven. The 'up to a minimal variation' citation for the quadratic reward is a serious gap: the Q-functions are not linear in φ, and Algorithm 2 optimizes a different objective from the one in the cited theorem. This is not a disagreement with consensus; it is an internally missing proof. The authors should be asked to provide a full regret analysis for the zero-reward-with-bonus algorithm under quadratic rewards, or to remove the dimension-only claim. The empirical section is preliminary but acceptable for a theory paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first paper to take MAIL beyond tabular games, and the non-interactive half of it is in good shape: the feature-level concentrability coefficient C_phi,max (Def 3.2) is a genuine idea, and the change-of-measure in Lemma D.6 is a real argument, not a placeholder. Given Assumptions 2.1 and 3.1, the BC bound (Thm 3.3) is coherent and worth reading. Second, the interactive claim (Thm 4.1) currently does not have a proof at its crux: Lemma 4.4 asserts that the LSVI-UCB regret bound extends \"up to a minimal variation\" to the quadratic, time-varying exploration rewards r=||phi||_{Lambda^-1}. That is exactly where the standard linear-Q argument breaks; the Q-functions for that reward are not linear in phi, and the paper gives no argument for the extension. So the headline dimension-only result is not yet supported.\n\nWhat else is soft: the claim C_phi,max <= C_max is asserted with examples but not proven generally; Assumption 3.1 excludes some Nash equilibria, as the paper admits in Appendix D; experiments are suggestive but underpowered (the \"three seeds\" list contains four values, no visible confidence bands, and the code link is not actually present). These are addressable, and the paper is honest about some of them in Appendix C.\n\nThe citation pattern is mostly fine: the same-group tabular papers and single-agent linear imitation are real prior work, and this is a clear extension of those lines. No fitted constants in the theory; C_phi,max is a definition, not a fitted quantity.\n\nWho it is for: anyone working on imitation learning in games or on offline RL with function approximation. It deserves a serious referee, but the referee should push hard on Lemma 4.4. If the authors can prove the quadratic-reward regret bound (or modify the algorithm so the standard analysis applies) and prove the C_phi,max comparison, I'd be comfortable with the paper. As it stands, I wouldn't cite Theorem 4.1 as a theorem.","headline":"First linear-function-approximation treatment of multi-agent imitation learning, with a useful new concentrability notion and a clean BC analysis—but the interactive theorem rests on an unproven extension of LSVI-UCB to quadratic rewards.","tokens_in":51234,"tokens_out":2017,"would_cite":true,"duration_ms":20857,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","91A26","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Imitation learning in linear Markov games is tractable: offline behavior cloning needs only a feature-level concentrability coefficient, and an interactive algorithm eliminates that coefficient entirely, scaling with the feature dimension d","keywords":["multi-agent imitation learning","linear Markov games","Nash equilibrium","behavioral cloning","concentrability coefficient","feature dimension","reward-free exploration","LSVI-UCB"],"falsifier":"Run LSVI-UCB-ZERO on a concrete two-state linear Markov game with features chosen so that the bonus ∥φ(x,a)∥_{Λ^{-1}} frequently changes; if the cumulative regret exceeds the O(H^2 d^{3/2} B √(K log K)) bound used in Lemma 4.4, the interactive guarantee collapses. Separately, build a linear Markov game whose only Nash equilibrium is an isolated pure strategy; the paper itself shows such equilibria may not be limits of softmax-linear policies, so checking whether the non-interactive bound holds in that game would settle the reach of Assumption 3.1.","tokens_in":50005,"feed_emoji":"🎮","tokens_out":6376,"duration_ms":60559,"temperature":0.7,"pith_summary":"This paper tries to show that multi-agent imitation learning becomes tractable when the underlying game has a linear structure. In the offline setting, it claims that behavior cloning can learn an approximate Nash equilibrium from expert trajectories using only a feature-level concentrability coefficient, which can be far smaller than the state-action concentrability required in tabular games. In the interactive setting, it claims a new algorithm, LSVI-UCB-ZERO-BC, whose sample complexity depends only on the feature dimension d and not the number of states, eliminating the concentrability coefficient altogether. If these claims hold, imitation learning in large or high-dimensional Markov games is possible without enumerating states, and the paper's deep extension suggests the same mechanism works with neural-network features.","feed_headline":"Imitation in linear games: sample cost follows d, not states","feed_subtitle":"A feature-level concentrability bound and an interactive no-concentrability algorithm make multi-agent imitation practical in large state sp","key_machinery":"The load-bearing object is the feature map φ(x,a) and the covariance matrices it induces. Linearity of transitions and rewards implies state-action value functions and state-occupancy measures are linear in φ, which lets the analysis change measure from the expert's state distribution to the feature expectation vector; the norm of that vector under the inverse covariance matrix is exactly the proposed concentrability coefficient C_φ,max. In the interactive algorithm, the same change of measure is applied with covariance matrices built from a reward-free exploration phase, in which LSVI-UCB is run with zero reward and a (β+1)-weighted quadratic bonus ∥φ(x,a)∥_{Λ^{-1}}; that exploration makes","core_discovery":"The central claim is that in linear Markov games—where transitions and rewards are linear in a known d-dimensional feature map φ—the hard quantity for imitation is not the state-level all-policy-deviation concentrability but a feature-level concentrability C_φ,max. Under this structure, behavioral cloning over the softmax-linear policy class produces an ε-Nash equilibrium using O~(H^5 C_φ,max^2 d B^2 / ε^2) expert trajectories. More strongly, the paper's interactive algorithm LSVI-UCB-ZERO-BC replaces the expert covariance matrix with one built from a zero-reward exploration phase, driving the weighted feature-norm of any deviation below O(d^{3/2} H^2 B sqrt(log/K)); with K = O~(H^6 d^4 B^4","pith_inferences":["If the unproved quadratic-reward extension of the LSVI-UCB regret bound is valid, the architecture gives a template: any no-regret linear MDP algorithm can be turned into a concentrability-free interactive MAIL learner by running it with zero reward and quadratic exploration bonuses.","C_φ,max could serve as a practical pre-deployment diagnostic: computing it from a candidate feature map would tell whether offline BC is safe, and an estimator of it would let the algorithm decide how many expert queries are needed when starting from existing data (the paper leaves this adaptive variant open).","The theory predicts a concrete testable tradeoff: as features become more compressive, C_φ,max tends down but realizability of the expert equilibrium becomes harder; evaluation of learned representations should therefore use the induced concentrability, not just prediction loss.","Since the interactive analysis avoids enumerating states entirely, the same no-regret-exploration idea may extend to general function approximation, where the feature map is the current critic's last layer—suggesting that the deep algorithm is not just a heuristic but a plausible instantiation of the same principle."],"forward_implications":["In linear Markov games, offline imitation by behavior cloning needs O~(H^5 C_φ,max^2 d B^2 / ε^2) expert trajectories for an ε-Nash, with C_φ,max ≤ C_max; the gap can be infinite in tabular cases.","Interactive imitation via LSVI-UCB-ZERO-BC attains ε-Nash with O~(H^6 d^4 B^4 / ε^2) episodes and O~(H^7 d^4 B^4 / ε^2) expert queries, independent of any concentrability coefficient and independent of the number of states.","The interactive guarantee transfers to discounted infinite-horizon linear Markov games, with a similar K-rate and no state-count dependence.","The deep extension DQN-Explore-BC, which uses the last layer of a DQN critic as the feature map driving the exploration bonus, outperforms plain deep BC in Tic-Tac-Toe and Connect4 against a range of opponents."],"fun_headline_variants":["Imitation in linear games: sample cost depends on d, not states","Linear Markov games: interactive imitation with no concentrability bound","Imitation learning in linear games: complexity scales with feature dimension","Sample-efficient imitation in linear Markov games via feature structure"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole analysis rests on the expert's Nash equilibrium being representable as a limit point of the softmax-linear policy class in the given features, and the interactive theorem additionally presumes, without proof, that the linear LSVI-UCB regret bound still holds when the exploration reward is quadratic in the features.","fun_headline_variants_meta":{"raw":{"variants":["Imitation in linear games: sample cost depends on d, not states","Linear Markov games: interactive imitation with no concentrability bound","Imitation learning in linear games: complexity scales with feature dimension","Sample-efficient imitation in linear Markov games via feature structure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000777,"raw_usage":{"total_tokens":3263,"prompt_tokens":726,"completion_tokens":2537,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":2476}},"tokens_in":470,"tokens_out":2537,"duration_ms":18306,"temperature":1.0,"reasoning_tokens":2476,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T20:37:14.073819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run LSVI-UCB-ZERO on a concrete two-state linear Markov game with features chosen so that the bonus ∥φ(x,a)∥_{Λ^{-1}} frequently changes; if the cumulative regret exceeds the O(H^2 d^{3/2} B √(K log K)) bound used in Lemma 4.4, the interactive guarantee collapses. Separately, build a linear Markov game whose only Nash equilibrium is an isolated pure strategy; the paper itself shows such equilibria may not be limits of softmax-linear policies, so checking whether the non-interactive bound holds in that game would settle the reach of Assumption 3.1.","supporting_citations":[],"review_version":1}