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

arXiv: https://arxiv.org/abs/2201.03522 · HTML: https://mlsanity.com/paper/2201.03522/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 41 references that are in the map.
- First posted on arXiv 10 Jan 2022.

## Builds on (most cited first, 26 of 26)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification](https://mlsanity.com/paper/2111.11188/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [Offline Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2108.01832/) (2021)
- [Feature-Based Q-Learning for Two-Player Stochastic Games](https://mlsanity.com/paper/1906.00423/) (2019)
- [Minimax Sample Complexity for Turn-based Stochastic Game](https://mlsanity.com/paper/2011.14267/) (2020)

## Built on by (most cited first, 28 of 28)

- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient](https://mlsanity.com/paper/2210.00750/) (2022)
- [O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2209.12430/) (2022)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Mitigating Preference Hacking in Policy Optimization with Pessimism](https://mlsanity.com/paper/2503.06810/) (2025)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Corruption-Robust Offline Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2403.07933/) (2024)
- [Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach](https://mlsanity.com/paper/2305.13289/) (2023)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Offline Equilibrium Finding](https://mlsanity.com/paper/2207.05285/) (2022)
- [Offline congestion games: How feedback type affects data coverage requirement](https://mlsanity.com/paper/2210.13396/) (2022)
- [Data Poisoning to Fake a Nash Equilibrium in Markov Games](https://mlsanity.com/paper/2306.08041/) (2023)
- [HCAG: Hierarchical Abstraction and Retrieval-Augmented Generation on Theoretical Repositories with LLMs](https://mlsanity.com/paper/2603.20299/) (2026)
- [Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learning](https://mlsanity.com/paper/2602.21020/) (2026)
- [Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2610.05968/) (2026)

## Abstract (arXiv)

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.