Pith. sign in

REVIEW 4 major objections 5 minor 36 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read 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

desk verdict 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. read the letter →

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

Luca Viano , Till Freihaut , Emanuele Nevali , Volkan Cevher , Matthieu Geist , Giorgia Ramponi This is my paper
classification cs.LG MSC 68T0591A2668Q32
keywords multi-agentimitationlearninglinearMarkovgamesNashequilibriumbehavioralcloningconcentrabilitycoefficientfeaturedimensionreward-freeexplorationLSVI-UCB
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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

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

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, 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 · score 4.0 of 10

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

  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.

Assumptions & free parameters 2 free parameters · 6 assumptions · 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.
assumptions (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
    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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi-agent imitation learning with function approximation: Linear Markov games and beyond." pith.science (2026). https://pith.science/paper/6DTJ5J2H

@misc{pith2026260222810,
  author       = {Pith},
  title        = {Pith review of: Multi-agent imitation learning with function approximation: Linear Markov games and beyond},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6DTJ5J2H}},
  note         = {Machine review of arXiv:2602.22810}
}
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 the authors.

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. 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 to comment.

Reference graph

Works this paper leans on

36 extracted references · 1 canonical work pages

  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,

    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,

    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,

    arXiv

Show all 36 references
  1. [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,

    2009 arXiv

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

    arXiv

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

    2006 arXiv

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

    1901 arXiv

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

    2011

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

    2018

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

    2020

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

    2020

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

    2002

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

    2002

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

    2015

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

    2021

  13. [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−δ...

    2020

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

    2025

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

    2021

  16. [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 (Res...

    2017

  17. [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),

    doi

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

    arXiv

  19. [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, t...

    2019

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

    arXiv

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

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

    1902 arXiv

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

    2007 arXiv

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

    arXiv

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

    2022

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

    arXiv

  27. [2024]

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

    arXiv

  28. [2025]

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

    arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.