When is Offline Two-Player Zero-Sum Markov Game Solvable?

Understand

We study what dataset assumption permits solving offline two-player zero-sum Markov games.

• In stark contrast to the offline single-agent Markov decision process, we show that the single strategy concentration assumption is insufficient for learning the Nash equilibrium (NE) strategy in offline two-player zero-sum Markov games.
• On the other hand, we propose a new assumption named unilateral concentration and design a pessimism-type algorithm that is provably efficient under this assumption.
• In addition, we show that the unilateral concentration assumption is necessary for learning an NE strategy.