# Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 8 Jun 2022.

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

- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Inference and Uncertainty Quantification for Noisy Matrix Completion](https://mlsanity.com/paper/1906.04159/) (2019)

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

- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Minimax-Optimal Multi-Agent Robust Reinforcement Learning](https://mlsanity.com/paper/2412.19873/) (2024)
- [Pessimism-Free Offline Learning in General-Sum Games via KL Regularization](https://mlsanity.com/paper/2605.00264/) (2026)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Data](https://mlsanity.com/paper/2403.11841/) (2024)
- [Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity](https://mlsanity.com/paper/2408.06544/) (2024)

## Abstract (arXiv)

This paper makes progress towards learning Nash equilibria in two-player zero-sum Markov games from offline data. Specifically, consider a γ-discounted infinite-horizon Markov game with S states, where the max-player has A actions and the min-player has B actions. We propose a pessimistic model-based algorithm with Bernstein-style lower confidence bounds -- called VI-LCB-Game -- that provably finds an varepsilon-approximate Nash equilibrium with a sample complexity no larger than fracC_mathsfclippedstarS(A+B)(1-γ)3varepsilon2 (up to some log factor). Here, C_mathsfclippedstar is some unilateral clipped concentrability coefficient that reflects the coverage and distribution shift of the available data (vis-`a-vis the target data), and the target accuracy varepsilon can be any value within big(0,frac11-γbig]. Our sample complexity bound strengthens prior art by a factor of minA,B, achieving minimax optimality for the entire varepsilon-range. An appealing feature of our result lies in algorithmic simplicity, which reveals the unnecessity of variance reduction and sample splitting in achieving sample optimality.