Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
 
conference paper

Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning

Freihaut, Till
•
Viano, Luca  
•
Cevher, Volkan  orcid-logo
Show more
December 2025
39th Conference on Neural Information Processing Systems (NeurIPS 2025) [forthcoming publication]
39th Conference on Neural Information Processing Systems (NeurIPS 2025)

This paper provides the first expert sample complexity characterization for learning a Nash equilibrium from expert data in Markov Games. We show that a new quantity named the all policy deviation concentrability coefficient is unavoidable in the non-interactive imitation learning setting, and we provide an upper bound for behavioral cloning (BC) featuring such coefficient. BC exhibits substantial regret in games with high concentrability coefficient, leading us to utilize expert queries to develop and introduce two novel solution algorithms: MAIL-BRO and MURMAIL. The former employs a best response oracle and learns an ε-Nash equilibrium with O(ε −4) expert and oracle queries. The latter bypasses completely the best response oracle at the cost of a worse expert query complexity of order O(ε −8). Finally, we provide numerical evidence, confirming our theoretical findings.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

13496_Learning_Equilibria_from.pdf

Type

Main Document

Version

Accepted version

Access type

openaccess

License Condition

N/A

Size

746.45 KB

Format

Adobe PDF

Checksum (MD5)

41dfd841221e64709156359eebd44b7c

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés