mlsanityData to 7 Oct 2026

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

arXiv 2206.04044 ↗First posted 8 Jun 2022cs.LG cs.GT cs.ITcited by 11

Not on the map. Why?

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.

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

Builds on

5 of 15 references.

References · 5

  1. 2018Human-level performance in first-person multiplayer games with population-based deep reinforcement learningcited by 260
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  3. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  4. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  5. 2019Inference and Uncertainty Quantification for Noisy Matrix Completioncited by 39

Built on by

Cited by year (2026 to 7 Oct)

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

11 papers.

  1. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  2. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  3. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  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. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 4
  7. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  8. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 3
  9. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  10. 2024Pessimistic Causal Reinforcement Learning with Mediators for Confounded Offline Datacited by 0
  11. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexitycited by 0