Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model. (arXiv:2208.10458v1 [cs.LG])

This paper is concerned with two-player zero-sum Markov games -- arguably the
most basic setting in multi-agent reinforcement learning -- with the goal of
learning a Nash equilibrium (NE) sample-optimally. All prior results suffer
from at least one of the two obstacles: the curse of multiple agents and the
barrier of long horizon, regardless of the sampling protocol in use. We take a
step towards settling this problem, assuming access to a flexible sampling
mechanism: the generative model. Focusing on …

arxiv games lg markov minimax rl