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

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 \emph{all policy deviation concentrability coefficient} (Freihaut et al., 2025b) 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 \emph{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.

(Problem) Teaching several AI agents to imitate expert behavior in a shared environment, such as a competitive game, is provably harder than teaching a single agent. The difficulty is that the agents must learn good behavior even in situations the expert demonstrations rarely covered, and prior theory showed this obstacle is unavoidable, but only for small games. (Solution) We study games whose dynamics and rewards follow patterns captured by a set of features, which lets agents transfer what they learn to new situations that look similar. We prove this makes learning from a fixed dataset much easier when the features are informative. To remove the reliance on good data coverage entirely, we design an interactive algorithm whose data needs grow only with the number of features, not the number of game situations. We then extend these ideas into a practical deep learning method. (Impact) Our method comes with provable guarantees and clearly outperforms behavior cloning on Tic-Tac-Toe and Connect Four.