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

2026-02-26 · Luca Viano, Till Freihaut, Emanuele Nevali, Volkan Cevher, Matthieu Geist, Giorgia Ramponi arxiv

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.

📄 PDF Abstract BibTeX arXiv:2602.22810

Code (0)

등록된 구현이 없습니다.

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation

2023-02-07 · Qiwen Cui, Kaiqing Zhang, Simon S. Du

We propose a new model, independent linear Markov game, for multi-agent reinforcement learning with a large state space and a large number of agents. This is a class of Markov games with independent linear function appro…

Multi-agent Reinforcement Learning

Refined Sample Complexity for Markov Games with Independent Linear Function Approximation

2024-02-11 · Yan Dai, Qiwen Cui, Simon S. Du

Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL). It was long believed that the "curse of multi-agents" (i.e., the algorithmic performance drops exponentially with the number of agent…

Multi-agent Reinforcement Learning

Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation

2021-08-19 · Zhihan Liu, Yufeng Zhang, Zuyue Fu, Zhuoran Yang 외

In generative adversarial imitation learning (GAIL), the agent aims to learn a policy from an expert demonstration so that its performance cannot be discriminated from the expert policy on a certain predefined reward set…

Imitation Learning

Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

2018-02-23 · ICML 2018 7 · Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang 외

We consider the problem of \emph{fully decentralized} multi-agent reinforcement learning (MARL), where the agents are located at the nodes of a time-varying communication network. Specifically, we assume that the reward …

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Gap-Dependent Bounds for Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

2026-02-23 · Haochen Zhang, Zhong Zheng, Lingzhou Xue arxiv

We study gap-dependent performance guarantees for nearly minimax-optimal algorithms in reinforcement learning with linear function approximation. While prior works have established gap-dependent regret bounds in this set…

Reinforcement Learning