Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

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

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 20:37 UTC pith:6DTJ5J2H

load-bearing objection 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. the 4 major comments →

arxiv 2602.22810 v2 pith:6DTJ5J2H submitted 2026-02-26 cs.LG

Multi-agent imitation learning with function approximation: Linear Markov games and beyond

Luca Viano , Till Freihaut , Emanuele Nevali , Volkan Cevher , Matthieu Geist , Giorgia Ramponi This is my paper
classification cs.LG MSC 68T0591A2668Q32
keywords multi-agent imitation learninglinear Markov gamesNash equilibriumbehavioral cloningconcentrability coefficientfeature dimensionreward-free explorationLSVI-UCB
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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

What carries the argument

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

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

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

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

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

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 (4)
  1. [Appendix E.2, Lemma 4.4] 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.
  2. [Lemma 4.4 proof, decreasing-reward step] 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.
  3. [Assumption 3.1 and Appendix D] 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.
  4. [Appendix G, Lemma G.1] 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.
minor comments (5)
  1. [Section 2.1, Assumption 2.1] 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.
  2. [Abstract and Section 1] 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.
  3. [Algorithm 2] 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.
  4. [Appendix H, Algorithm 5] 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.
  5. [Lemma J.4] 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.

Circularity Check

1 steps flagged

No fitted-parameter circularity; one load-bearing step assumes quadratic-reward regret bound via self-citation, leaving the interactive sample complexity conditional.

specific steps
  1. ansatz smuggled in via citation [Appendix E.2, Proof of Lemma 4.4 (footnote 8)]
    "invoking Viano et al. [2024, Theorem 6] 8 we obtain Regret(π⋆)≤O(H^2 d^{3/2} B√(K log(Kδ^{-1}))). 8This is up to a minimal variation to accommodate quadratic rewards instead of linear ones..."

    The exploratory reward in Lemma 4.4 is r^k_h(x,a)=||φ(x,a)||_{(Λ^{k,h})^{-1}}, quadratic in φ, so the Q-functions are not in the linear span of φ and the cited LSVI-UCB regret bound (stated for r=φ^Tθ) does not apply. The proof supplies no argument beyond 'up to a minimal variation'; it thereby assumes the exact regret bound needed to prove Lemma 4.4. Since Lemma 4.4 is the step that removes the concentrability/Cφ,max dependence in Theorem 4.1, the interactive dimension-only bound is conditional on an unproven self-citational extension, not derived from stated assumptions.

full rationale

The paper is not circular in the fitted-parameter or definitional sense: there are no fitted constants, Theorem 3.3's Cφ,max is a definition rather than a fitted value, and Assumption 3.1 is an explicit realizability assumption whose limitations the paper acknowledges with a concrete counterexample in Appendix D. The non-interactive analysis (change of measure, MLE guarantees) is self-contained and does not reduce to its input. The interactive analysis, however, contains a single load-bearing self-citational step: Lemma 4.4 claims a O(K^{-1/2}) decay for the weighted feature norm of any expected feature vector, and its proof invokes Viano et al. [2024, Thm 6] for a regret bound that is proven for linear rewards, while the exploratory reward used by Algorithm 2 is quadratic in φ. The footnote-style 'minimal variation' is not a proof; it smuggles the needed quadratic-reward regret bound through a citation from overlapping authors. If that extension is false, Theorem 4.1's dimension-only interactive sample complexity loses its support. This is a correctness/justification gap rather than an equivalence-by-construction, so the circularity score is moderate rather than high. All other dependencies on same-group prior work (Freihaut et al. 2025b, Moulin et al. 2025b) are either external lower bounds, tabular baselines, or explicit algorithmic extensions, and are not used to define away the target result.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 1 invented entities

The theory is a parameter-free derivation in the sense that no constants are fitted to reach the theorems; lambda and eta are analysis-determined regularizers/temperatures. The load-bearing load sits on (i) the independent linear Markov game assumption (Assumption 2.1), (ii) the expert-realizability assumption (Assumption 3.1) which the authors themselves show excludes some Nash equilibria, and (iii) three external same-group theorems (Freihaut 2025a,b; Viano et al. 2024; Moulin et al. 2025b), one of which is invoked with an unproven 'minimal variation' to quadratic rewards.

free parameters (2)
  • lambda (feature-covariance regularization) = lambda = 1/tau_E in Theorem 3.3; lambda = 1 in Algorithm 2 (Lambda_0 = I); lambda = 1.5 in the deep experiments (Appendi
    Regularizer in Lambda = sum phi phi^T + lambda I. The theory chooses lambda = 1/tau_E to balance bias and variance; the deep experiments hand-set 1.5 for invertibility. This is an analysis/implementation choice, not a fitted constant needed by the theorems.
  • eta (inverse temperature of the policy class Pi_softlin) = eta = log(tau_E)/H (non-interactive, Thm 3.3); eta = log(K)/H (interactive, Lemma 4.5)
    Chosen in the analysis to balance MLE estimation error against misspecification error of the softmax-linear class. It is a proof-determined parameter, not a data-fitted value.
axioms (6)
  • domain assumption Assumption 2.1: stationary linear Markov games — known d-dimensional features phi(x,a_n) with transition and reward linear in phi when the opponent's policy is frozen: P(x'|x,a_n,pi_-n) = phi(x,a_n)^T M_-n(x'), r_n = phi(x,a_n)^T w_-n.
    Load-bearing structural assumption imported from Cui et al. 2023. Everything in the paper (feature-level change of measure, linear Q-functions, covariance arguments) depends on it. It is standard in the linear-MDP literature but a genuine restriction on the game class.
  • ad hoc to paper Assumption 3.1: the expert Nash equilibrium is in the limit points of the softmax-linear policy class Pi_softlin, i.e., pi^n_E in lim_{eta->inf} Pi^n_softlin.
    Required for the non-interactive BC sample-complexity bound (Theorem 3.3). The paper itself flags the limitation and provides a normal-form-game example of a Nash equilibrium violating it (Appendix D), so the headline BC guarantee does not cover deterministic/pure expert equilibria.
  • domain assumption Boundedness: ||phi(x,a)||_2 <= 1, max(||M||_2, ||w||_2) <= B, rewards in [-1,1], ||theta|| <= B_theta.
    Standard normalizations (Jin et al. 2019) used throughout the proofs; required for the cumulative-regret and elliptical-potential arguments in Appendices D, E, and G.
  • ad hoc to paper External regret bound: LSVI-UCB (and RMAX-RAVI-LSVI-UCB in the discounted case) achieves regret O-tilde(H^2 d^{3/2} B sqrt(K)) against the synthetic exploratory rewards r^k = ||phi||_{(Lambda^k)^{-1}}, asserted as 'up to a minimal variation' of Viano et al. [2024, Thm 6] (App. E.2) and of Moulin et
    This is the crux of Lemma 4.4 and Lemma G.1. The quadratic, non-linear-in-phi reward is not covered by the standard LSVI-UCB analysis, and no proof of the extension is supplied in the manuscript.
  • standard math MLE concentration for adaptively sampled states under misspecification (Lemma J.4, following Agarwal et al. 2020 and Rohatgi et al. 2025).
    Used to bound Delta_TV^2 (Lemma 4.5) and in Theorem D.5. Adopted as a black-box external lemma; its own assumptions (martingale structure, bounded log-ratios) are stated in Appendix J.
  • domain assumption Quantal response equilibria exist and Pi_softlin realizes them (Lemma D.4, using McKelvey and Palfrey 1995).
    Justifies calling Assumption 3.1 weak by relating softmax-linear policies to QRE limits, while the paper simultaneously notes non-isolated Nash equilibria that cannot be obtained as QRE limits.
invented entities (1)
  • Feature-level concentrability coefficient C_phi,max no independent evidence
    purpose: New complexity measure (Definition 3.2) replacing the state-action-level all-policy-deviation coefficient C_max in the BC and interactive bounds; formalizes how well the expert's feature covariance covers feature directions reachable by best responses.
    A formal quantity defined from the problem data (phi, expert occupancy covariance), not an empirically falsifiable object. Its usefulness is that it appears inside proven bounds; the claimed property C_phi,max <= C_max for general features is asserted, not proven.

pith-pipeline@v1.3.0-alltime-deepseek · 49644 in / 29470 out tokens · 265472 ms · 2026-08-02T20:37:14.073819+00:00 · methodology

0 comments
read the original abstract

In this work, we present the first theoretical analysis of multi-agent imitation learning (MAIL) in linear Markov games where both the transition dynamics and each agent's reward function are linear in some given features. We demonstrate that by leveraging this structure, it is possible to replace the state-action level "all policy deviation concentrability coefficient" (Freihaut et al., arXiv:2510.09325) with a concentrability coefficient defined at the feature level which can be much smaller than the state-action analog when the features are informative about states' similarity. Furthermore, to circumvent the need for any concentrability coefficient, we turn to the interactive setting. We provide the first, computationally efficient, interactive MAIL algorithm for linear Markov games and show that its sample complexity depends only on the dimension of the feature map $d$. Building on these theoretical findings, we propose a deep MAIL interactive algorithm which clearly outperforms BC on games such as Tic-Tac-Toe and Connect4.

Figures

Figures reproduced from arXiv: 2602.22810 by Emanuele Nevali, Giorgia Ramponi, Luca Viano, Matthieu Geist, Till Freihaut, Volkan Cevher.

Figure 1
Figure 1. Figure 1: Experimental results in the linear Gridworld ((a), (b)) and deep Tic-Tac-Toe case ((c)). [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of exploration algorithms The chain experiment The same conclusion does not carry over to the experiment in the chain environment reported in [PITH_FULL_IMAGE:figures/full_fig_p054_2.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation

    cs.LG 2026-05 unverdicted novelty 7.0

    MA-BC partitions divergent expert data while pooling non-conflicting pairs in MOMDPs, converging faster to Pareto-optimal policies than independent learners and matching a new minimax lower bound.

  2. Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation

    cs.LG 2026-05 unverdicted novelty 7.0

    MA-BC partitions divergent expert data and pools non-conflicting pairs to achieve faster convergence to Pareto-optimal policies in MOMDPs, with a matching minimax lower bound.

Reference graph

Works this paper leans on

36 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    Definition D.3

    which leverages the concept of Quantile Response Equilibria in a normal form game is defined as follows. Definition D.3. Quantile Response Equilibria.LetQbe a collection of payoff matrices {Q1, . . . , QN }. We define the regularize payoff matrix for the playern∈[N] ˜Q(a1, . . . , aN ) =Q(a 1, . . . , aN )− 1 η X an∈An π(an) logπ(a n) 6This fact is needed...

    1995

  2. [2]

    At this point, we can upper bound the sum of the expected local Hellinger divergences with the divergence between trajectories invoking Rohatgi et al

    At this point, we upper bound the total variation distance by the Hellinger divergence EX∼ν πE h TV2(πn out,h, πn E,h)(X) ≤4E X∼ν πE h D2 Hel(πn out,h, πn E,h)(X) whereD Hel is the Hellinger divergence defined as D2 Hel(p, q) = X z∈Z p p(z)− p q(z) 2 for somep, q∈∆ Z for some finite setZ. At this point, we can upper bound the sum of the expected local Hel...

    2025

  3. [3]

    The most important change is a change of notation

    The conceptual idea of both algorithms is identical. The most important change is a change of notation. While in the 2 player setting we set active =−n which is only one player, here we need to change to active = n to ensure again that only one player is actively exploring. That being said, we can continue with the theoretical result for theN-players case...

    2024

  4. [5]

    D. J. Foster, A. Block, and D. Misra. Is behavior cloning all you need? understanding horizon in imitation learning.arXiv preprint arXiv:2407.15007,

    Pith/arXiv arXiv

  5. [6]

    Freihaut, L

    T. Freihaut, L. Viano, V. Cevher, M. Geist, and G. Ramponi. Learning equilibria from data: Provably efficient multi-agent imitation learning, 2025a. URLhttps://arxiv.org/abs/2505. 17610. T. Freihaut, L. Viano, E. Nevali, V. Cevher, M. Geist, and G. Ramponi. Rate optimal learning of equilibria from data.arXiv preprint arXiv:2510.09325, 2025b. D. Garg, S. C...

    arXiv

  6. [7]

    Therefore, Π n softlin is richer and more likely to realize the observe expert behaviour for largeη

    Our assumption is less restrictive than this because we can realize even action value functions which are not attained by an equilibrium profile. Therefore, Π n softlin is richer and more likely to realize the observe expert behaviour for largeη. We now have all the elements to state the main result for non-interactive imitation learning in generalN-playe...

    2019

  7. [8]

    URL https://arxiv.org/abs/1709.01507. B. Huang, J. D. Lee, Z. Wang, and Z. Yang. Towards general function approximation in zero-sum markov games,

    Pith/arXiv arXiv

  8. [13]

    Rohatgi, A

    D. Rohatgi, A. Block, A. Huang, A. Krishnamurthy, and D. J. Foster. Computational-statistical tradeoffs at the next-token prediction barrier: Autoregressive and imitation learning under mis- specification.arXiv preprint arXiv:2502.12465,

    Pith/arXiv arXiv

  9. [16]

    URLhttps://arxiv.org/abs/2009.14471. L. Viano, A. Kamoutsi, G. Neu, I. Krawczuk, and V. Cevher. Proximal point imitation learning. Advances in Neural Information Processing Systems, 35:24309–24326,

    Pith/arXiv arXiv 2009

  10. [17]

    URLhttps://openreview.net/forum?id=DChQpB4AJy. 17 S. Viel, L. Viano, and V. Cevher. Il-soar: Imitation learning with soft optimistic actor critic.arXiv preprint arXiv:2502.19859,

    Pith/arXiv arXiv

  11. [18]

    URLhttps://proceedings.mlr.press/v162/wagenmaker22b.html. R. Wang, S. S. Du, L. Yang, and R. R. Salakhutdinov. On reward-free reinforcement learning with linear function approximation.Advances in neural information processing systems, 33: 17816–17826, 2020a. R. Wang, S. S. Du, L. F. Yang, and R. Salakhutdinov. On reward-free reinforcement learning with li...

    Pith/arXiv arXiv 2006

  12. [19]

    URLhttps://arxiv.org/abs/ 1901.00210. X. Zhang, Y. Ma, and A. Singla. Task-agnostic exploration in reinforcement learning.Advances in Neural Information Processing Systems, 33:11734–11743,

    Pith/arXiv arXiv 1901

  13. [20]

    18 Contents of Appendix This appendix provides supplementary material to support the main findings of the paper

    URLhttps://proceedings.mlr.press/ v162/zhong22b.html. 18 Contents of Appendix This appendix provides supplementary material to support the main findings of the paper. •Appx. A contains a summary table of all the notation used throughout this work. •Appx. B provides an extensive discussion on related works, in particular it includestheoretical multi-agent ...

    2011

  14. [21]

    and therefore does not extend to the discounted infinite horizon setting. In contrast, we provide the first analysis of multi-agent imitation learning with linear function approximation, applicable to both finite horizon and discounted infinite horizon settings, thereby addressing the open questions highlighted by Freihaut et al. [2025b]. Deep multi-agent...

    2018

  15. [23]

    Reward-free reinforcement learning.Reward free reinforcement learning was first introduced in the seminal work of Jin et al

    consider settings in which demonstrations may originate from suboptimal experts and propose a two stage approach that first classifies trajectories as expert or non expert before learning a robust policy from the labeled data. Reward-free reinforcement learning.Reward free reinforcement learning was first introduced in the seminal work of Jin et al. [2020...

    2020

  16. [24]

    In these situations, our algorithms could still be applied but the theoretical guarantees would not hold

    it does exclude some Nash Equilibria that might be observed in the dataset. In these situations, our algorithms could still be applied but the theoretical guarantees would not hold. It would be therefore interesting to drop completely Assumption 3.1 and develop a method that relies only on structural properties of the game. A possible solution would be bu...

    2020

  17. [27]

    As a practical example of a Nash equilibrium we can recover consider the zero sum normal form games with payoff matrix 1 0 1 0

    Changing the initial value ofη, different limits can be obtained but there are also some (non-isolated) Nash equilibria which can not be recovered as limit of a QRE, namely the isolated Nash equilibria. As a practical example of a Nash equilibrium we can recover consider the zero sum normal form games with payoff matrix 1 0 1 0 . For the row player every ...

    2002

  18. [29]

    We notice that Lemma 4.3 avoids completely the dependence onC φ,max.Instead it is replaced with maxπ−n∈Π−n φ πn E ,π−n, h (Λ−n,K h )−1

    This is given in Lemma 4.3. We notice that Lemma 4.3 avoids completely the dependence onC φ,max.Instead it is replaced with maxπ−n∈Π−n φ πn E ,π−n, h (Λ−n,K h )−1 . The main difference between the two quantities is that in Λ −n,K h the features are evaluated at the states and actions sampled while running LSVI-UCB-ZERO and not via Nash vs Nash dynamics. N...

    2002

  19. [31]

    Note that multiple Nash equilibria exist

    In particular, we fix the deterministic starting state ((1,0),(2,1)), from which both players require exactly five steps to reach the goal. Note that multiple Nash equilibria exist. All of the existing Nash equilibria have in common that no path lets the other agent reach the goal first. For Figure 1 (a) we take a convex combination of Nash equilibrium st...

    2015

  20. [33]

    The action spaces are discrete, consisting of 9 actions for Tic-Tac-Toe (corresponding to the grid cells) and 7 actions for Connect4 (corresponding to the columns)

    Consequently, the input dimensions are 2×3×3 for Tic-Tac-Toe and 2×6×7 for Connect4. The action spaces are discrete, consisting of 9 actions for Tic-Tac-Toe (corresponding to the grid cells) and 7 actions for Connect4 (corresponding to the columns). Both environments are treated as zero-sum games with sparse rewards: agents receive a reward of +1 for winn...

    2021

  21. [35]

    − 1 2 KX i=1 log πE(AE i |Xi) ˆπϵ(AE i |Xi) −log|C ϵ(log Πsoftlin)| − KX i=1 logE

    Therefore, by the Chernoff bound, we have that P " − 1 2 KX i=1 log πE(AE i |Xi) ˆπϵ(AE i |Xi) −log|C ϵ(log Πsoftlin)| − KX i=1 logE " e − 1 2 log πE( ¯AE i | ¯Xi) ˆπϵ( ¯AE i | ¯Xi) F E i # ≥t # ≤ 1 et . Therefore, settingt= log(1/δ), we have that with probability at least 1−δ, − 1 2 KX i=1 log πE(AE i |Xi) ˆπϵ(AE i |Xi) − KX i=1 logE " e − 1 2 log πE( ¯A...

    2020

  22. [36]

    [2025, Lemma F.4] withη= 1, we obtain that KX i=1 E " f πE(AE i |Xi) ¯π(AE i |Xi) 2 F E i # ≤4(2 + logB ratio) KX i=1 E f πE(AE i |Xi) ¯π(AE i |Xi) F E i

    Therefore, applying Rohatgi et al. [2025, Lemma F.4] withη= 1, we obtain that KX i=1 E " f πE(AE i |Xi) ¯π(AE i |Xi) 2 F E i # ≤4(2 + logB ratio) KX i=1 E f πE(AE i |Xi) ¯π(AE i |Xi) F E i . Therefore, replacing in (11), we obtain KX i=1 f πE(AE i |Xi) ¯π(AE i |Xi) ≤9 KX i=1 E f πE(AE i |Xi) ¯π(AE i |Xi) F E i + (1 + logBratio) log 1 δ . Finally, invoking...

    2025

  23. [80]

    This model is parameterized as a multi-layer feedforward network designed to improve representation learning while maintaining linear transformations

    Finally, we evaluate a deep Linear Policy as the BC policy. This model is parameterized as a multi-layer feedforward network designed to improve representation learning while maintaining linear transformations. The architecture consists of a sequence of linear layers with decreasing hidden widths. Specifically, it maps the flattened state (9) to a hidden ...

    2021

  24. [100]

    To address this, we employ an advanced neural architecture inspired by AlphaGo [Silver et al., 2017]

    In Connect4, the state space is significantly more complex than Tic-Tac-Toe, comprising over 4×10 12 feasible board positions. To address this, we employ an advanced neural architecture inspired by AlphaGo [Silver et al., 2017]. Specifically, we utilize a Residual Network (ResNet) adapted for the 6×7 board dimensions. The network begins with an initial co...

    2017

  25. [1989]

    URLhttps://doi.org/10.1137/1031049

    doi: 10.1137/ 1031049. URLhttps://doi.org/10.1137/1031049. J. Ho and S. Ermon. Generative adversarial imitation learning. InAdvances in Neural Information Processing Systems (NeurIPS),

    work page doi:10.1137/1031049

  26. [2013]

    URLhttps://arxiv.org/abs/1312.5602. A. Moulin, G. Neu, and L. Viano. Inverse q-learning done right: Offline imitation learning in qπ-realizable mdps, 2025a. URLhttps://arxiv.org/abs/2505.19946. A. Moulin, G. Neu, and L. Viano. Optimistically optimistic exploration for provably efficient infinite-horizon reinforcement and imitation learning.arXiv preprint ...

    Pith/arXiv arXiv

  27. [2016]

    from the single agent to the multi-agent setting. Their analysis relies on strong assumptions, such as the existence of a unique Nash equilibrium, and their empirical evaluation focuses on recovering policies 21 with high value rather than minimizing the Nash gap. Therefore, this work can be seen orthogonal to ours. Another non-cooperative line of work st...

    2019

  28. [2017]

    URLhttps://arxiv.org/ abs/1712.01815. J. Song, H. Ren, D. Sadigh, and S. Ermon. Multi-agent generative adversarial imitation learn- ing. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett, editors,Advances in Neural Information Processing Systems, volume

    Pith/arXiv arXiv

  29. [2018]

    URLhttps://proceedings.neurips.cc/paper_files/paper/2018/file/ 240c945bb72980130446fc2b40fbb8e0-Paper.pdf. W. Sun, A. Vemula, B. Boots, and D. Bagnell. Provably efficient imitation learning from observation alone. InInternational conference on machine learning, pages 6036–6045. PMLR,

    2018

  30. [2019]

    URLhttps://arxiv.org/abs/1902.06223. Q. Cui, K. Zhang, and S. S. Du. Breaking the curse of multiagents in a large state space: Rl in markov games with independent linear function approximation,

    Pith/arXiv arXiv 1902

  31. [2020]

    URLhttps://arxiv.org/abs/ 2007.13442. J. Perolat, B. Scherrer, B. Piot, and O. Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In F. Bach and D. Blei, editors,Proceedings of the 32nd International Conference on Machine Learning, volume 37 ofProceedings of Machine Learning Research, pages 1321–1329, Lille, France, 07–09 Jul

    Pith/arXiv arXiv 2007

  32. [2021]

    URLhttps://arxiv.org/abs/2107.14702. C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation,

    Pith/arXiv arXiv

  33. [2022]

    URLhttp: //dx.doi.org/10.1109/PDGC56933.2022.10053317

    doi: 10.1109/pdgc56933.2022.10053317. URLhttp: //dx.doi.org/10.1109/PDGC56933.2022.10053317. 15 E. Kaufmann, P. M´ enard, O. Darwiche Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In V. Feldman, K. Ligett, and S. Sabato, editors,Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132...

    arXiv 2022

  34. [2023]

    org/abs/2302.03673

    URLhttps://arxiv. org/abs/2302.03673. S. Eibelsh¨ auser and D. Poensgen. Markov quantal response equilibrium and a homotopy method for computing and selecting markov perfect equilibria of dynamic stochastic games.Available at SSRN 3314404,

    Pith/arXiv arXiv

  35. [2024]

    T. V. Bui, T. Mai, and H. T. Nguyen. Misodice: Multi-agent imitation from unlabeled mixed- quality demonstrations.arXiv preprint arXiv:2505.18595,

    Pith/arXiv arXiv

  36. [2025]

    URLhttps: //arxiv.org/abs/2507.05267. 14 A. Cohen, T. Koren, and Y. Mansour. Learning linear-quadratic regulators efficiently with only√ Tregret,

    Pith/arXiv arXiv