  Multi-agent reinforcement learning (MARL) is often modeled using the
framework of Markov games (also called stochastic games or dynamic games). Most
of the existing literature on MARL concentrates on zero-sum Markov games but is
not applicable to general-sum Markov games. It is known that the best-response
dynamics in general-sum Markov games are not a contraction. Therefore,
different equilibria in general-sum Markov games can have different values.
Moreover, the Q-function is not sufficient to completely characterize the
equilibrium. Given these challenges, model based learning is an attractive
approach for MARL in general-sum Markov games.
  In this paper, we investigate the fundamental question of \emph{sample
complexity} for model-based MARL algorithms in general-sum Markov games. We
show two results. We first use Hoeffding inequality based bounds to show that
$\tilde{\mathcal{O}}( (1-\gamma)^{-4} \alpha^{-2})$ samples per state-action
pair are sufficient to obtain a $\alpha$-approximate Markov perfect equilibrium
with high probability, where $\gamma$ is the discount factor, and the
$\tilde{\mathcal{O}}(\cdot)$ notation hides logarithmic terms. We then use
Bernstein inequality based bounds to show that $\tilde{\mathcal{O}}(
(1-\gamma)^{-1} \alpha^{-2} )$ samples are sufficient. To obtain these results,
we study the robustness of Markov perfect equilibrium to model approximations.
We show that the Markov perfect equilibrium of an approximate (or perturbed)
game is always an approximate Markov perfect equilibrium of the original game
and provide explicit bounds on the approximation error. We illustrate the
results via a numerical example.
