mlsanityData to 7 Oct 2026

Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets

arXiv 2202.07511 ↗First posted 15 Feb 2022cs.LG cs.GT stat.MLcited by 42

Not on the map. Why?

Cited by 23 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

We study episodic two-player zero-sum Markov games (MGs) in the offline setting, where the goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori. When the dataset does not have uniform coverage over all policy pairs, finding an approximate NE involves challenges in three aspects: (i) distributional shift between the behavior policy and the optimal policy, (ii) function approximation to handle large state space, and (iii) minimax optimization for equilibrium solving. We propose a pessimism-based algorithm, dubbed as pessimistic minimax value iteration (PMVI), which overcomes the distributional shift by constructing pessimistic estimates of the value functions for both players and outputs a policy pair by solving NEs based on the two value functions. Furthermore, we establish a data-dependent upper bound on the suboptimality which recovers a sublinear rate without the assumption on uniform coverage of the dataset. We also prove an information-theoretical lower bound, which suggests that the data-dependent term in the upper bound is intrinsic. Our theoretical results also highlight a notion of "relative uncertainty", which characterizes the necessary and sufficient condition for achieving sample efficiency in offline MGs. To the best of our knowledge, we provide the first nearly minimax optimal result for offline MGs with function approximation.

Key facts. Cited by 42 papers in the map (data through 7 Oct 2026). Builds on 25 of its 47 references that are in the map. First posted on arXiv 15 Feb 2022.

Builds on

25 of 47 references.

References · 25

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,406
  3. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  4. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  5. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  6. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  7. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  10. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  11. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  12. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
13 more
  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  3. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  5. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  6. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  7. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  8. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  9. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  10. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  11. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  12. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  13. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 13; 2024: 9; 2025: 3; 2026: 9.

42 papers.

Sort:

By area:

  1. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  2. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  4. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  5. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  6. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  7. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  8. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  9. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  10. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  11. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  12. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
30 more
  1. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  2. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  3. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  4. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  5. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  6. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  7. 2023Off-the-Grid MARL: Datasets with Baselines for Offline Multi-Agent Reinforcement Learningcited by 7
  8. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  9. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  10. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  11. 2024Adversarially Robust Decision Transformercited by 4
  12. 2024On Feasible Rewards in Multi-Agent Inverse Reinforcement Learningcited by 4
  13. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learningcited by 4
  14. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  15. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  16. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 3
  17. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
  18. 2022Offline Equilibrium Findingcited by 2
  19. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  20. 2025Learning an Optimal Assortment Policy under Observational Datacited by 2
  21. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  22. 2024Offline Fictitious Self-Play for Competitive Gamescited by 1
  23. 2024Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Modelscited by 1
  24. 2026Multi-agent imitation learning with function approximation: Linear Markov games and beyondcited by 1
  25. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learningcited by 1
  26. 2025Oryx: a Scalable Sequence Model for Many-Agent Coordination in Offline MARLcited by 0
  27. 2026Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitionscited by 0
  28. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  29. 2026Out-of-Distribution Generalisation with Sequence Models in Offline Multi-Agent Reinforcement Learningcited by 0
  30. 2026Inference-Time Nash Alignmentcited by 0