mlsanityData to 7 Oct 2026

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

arXiv 2201.03522 ↗First posted 10 Jan 2022cs.LG cs.AI cs.GTcited by 27

Not on the map. Why?

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.

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

Builds on

26 of 41 references.

References · 26

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  2. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  3. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  7. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  8. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  9. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  10. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  11. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  12. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
14 more
  1. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  2. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  3. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  4. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  5. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  6. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  7. 2021Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectificationcited by 59
  8. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  9. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  10. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  11. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  12. 2021Offline Decentralized Multi-Agent Reinforcement Learningcited by 32
  13. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 23
  14. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 11; 2023: 11; 2024: 2; 2025: 1; 2026: 2.

27 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  4. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  5. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  6. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  7. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  8. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
  9. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  10. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  11. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  12. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
15 more
  1. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  2. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  3. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  4. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  5. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  6. 2025Mitigating Preference Hacking in Policy Optimization with Pessimismcited by 7
  7. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  8. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  9. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  10. 2022Offline Equilibrium Findingcited by 2
  11. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  12. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  13. 2023Data Poisoning to Fake a Nash Equilibrium in Markov Gamescited by 1
  14. 2026HCAG: Hierarchical Abstraction and Retrieval-Augmented Generation on Theoretical Repositories with LLMscited by 1
  15. 2026Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Offline Fictitious Self-Play for Competitive Games
  2. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning
  3. 2026NashDreamer: Model-Based Reinforcement Learning for Zero-Sum Imperfect-Information Games
  4. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularization
  5. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  6. 2024Scalable Offline Reinforcement Learning for Mean Field Games
  7. 2026Bayesian Learning in Episodic Zero-Sum Games
  8. 2021Reinforcement Learning In Two Player Zero Sum Simultaneous Action Games