  We study multi-agent general-sum Markov games with nonlinear function
approximation. We focus on low-rank Markov games whose transition matrix admits
a hidden low-rank structure on top of an unknown non-linear representation. The
goal is to design an algorithm that (1) finds an $\varepsilon$-equilibrium
policy sample efficiently without prior knowledge of the environment or the
representation, and (2) permits a deep-learning friendly implementation. We
leverage representation learning and present a model-based and a model-free
approach to construct an effective representation from the collected data. For
both approaches, the algorithm achieves a sample complexity of
poly$(H,d,A,1/\varepsilon)$, where $H$ is the game horizon, $d$ is the
dimension of the feature vector, $A$ is the size of the joint action space and
$\varepsilon$ is the optimality gap. When the number of players is large, the
above sample complexity can scale exponentially with the number of players in
the worst case. To address this challenge, we consider Markov games with a
factorized transition structure and present an algorithm that escapes such
exponential scaling. To our best knowledge, this is the first sample-efficient
algorithm for multi-agent general-sum Markov games that incorporates
(non-linear) function approximation. We accompany our theoretical result with a
neural network-based implementation of our algorithm and evaluate it against
the widely used deep RL baseline, DQN with fictitious play.
