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

2022/01/10 by Qiwen Cui, Simon S. Du, Cui, Qiwen +1
Computer Science · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Opinion Dynamics and Social Influence #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2201.03522

openalex publication_date 2022/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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. Furthermore, our algorithm can achieve minimax sample complexity without any modification for two widely studied settings: dataset with uniform concentration assumption and turn-based Markov games. Our work serves as an important initial step towards understanding offline multi-agent reinforcement learning.

Related

• Offline Learning in Markov Games with General Function Approximation
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games
• Corruption-Robust Offline Two-Player Zero-Sum Markov Games