Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
  Sample Complexity
  Model-based reinforcement learning (RL), which finds an optimal policy using
an empirical model, has long been recognized as one of the corner stones of RL.
It is especially suitable for multi-agent RL (MARL), as it naturally decouples
the learning and the planning phases, and avoids the non-stationarity problem
when all agents are improving their policies simultaneously using samples.
Though intuitive and widely-used, the sample complexity of model-based MARL
algorithms has not been fully investigated. In this paper, our goal is to
address the fundamental question about its sample complexity. We study arguably
the most basic MARL setting: two-player discounted zero-sum Markov games, given
only access to a generative model. We show that model-based MARL achieves a
sample complexity of $\tilde O(|S||A||B|(1-\gamma)^{-3}\epsilon^{-2})$ for
finding the Nash equilibrium (NE) value up to some $\epsilon$ error, and the
$\epsilon$-NE policies with a smooth planning oracle, where $\gamma$ is the
discount factor, and $S,A,B$ denote the state space, and the action spaces for
the two agents. We further show that such a sample bound is minimax-optimal (up
to logarithmic factors) if the algorithm is reward-agnostic, where the
algorithm queries state transition samples without reward knowledge, by
establishing a matching lower bound. This is in contrast to the usual
reward-aware setting, with a
$\tilde\Omega(|S|(|A|+|B|)(1-\gamma)^{-3}\epsilon^{-2})$ lower bound, where
this model-based approach is near-optimal with only a gap on the $|A|,|B|$
dependence. Our results not only demonstrate the sample-efficiency of this
basic model-based approach in MARL, but also elaborate on the fundamental
tradeoff between its power (easily handling the more challenging
reward-agnostic case) and limitation (less adaptive and suboptimal in
$|A|,|B|$), particularly arises in the multi-agent context.
