mlsanityData to 7 Oct 2026

Offline Learning in Markov Games with General Function Approximation

arXiv 2302.02571 ↗First posted 6 Feb 2023cs.LG cs.AI cs.MAcited by 16

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

We study offline multi-agent reinforcement learning (RL) in Markov games, where the goal is to learn an approximate equilibrium -- such as Nash equilibrium and (Coarse) Correlated Equilibrium -- from an offline dataset pre-collected from the game. Existing works consider relatively restricted tabular or linear models and handle each equilibria separately. In this work, we provide the first framework for sample-efficient offline learning in Markov games under general function approximation, handling all 3 equilibria in a unified manner. By using Bellman-consistent pessimism, we obtain interval estimation for policies' returns, and use both the upper and the lower bounds to obtain a relaxation on the gap of a candidate policy, which becomes our optimization objective. Our results generalize prior works and provide several additional insights. Importantly, we require a data coverage condition that improves over the recently proposed "unilateral concentrability". Our condition allows selective coverage of deviation policies that optimally trade-off between their greediness (as approximate best responses) and coverage, and we show scenarios where this leads to significantly better guarantees. As a new connection, we also show how our algorithmic framework can subsume seemingly different solution concepts designed for the special case of two-player zero-sum games.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 40 of its 53 references that are in the map. First posted on arXiv 6 Feb 2023.

Builds on

40 of 53 references.

Closest ancestors · 18

Same direction, newest first

  1. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus1 Jun
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  6. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  7. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  8. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  9. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  10. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  11. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  12. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
6 more
  1. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  2. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  3. 2020Batch Value-function Approximation with Only Realizability11 Aug
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  6. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 22

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  6. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  7. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  8. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  9. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  10. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  11. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  12. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
10 more
  1. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  2. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  3. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  4. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  5. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  6. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  7. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  8. 2022Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescited by 11
  9. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  10. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 3; 2026: 9.

16 papers.

Sort:

By area:

  1. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  4. 2025Mitigating Preference Hacking in Policy Optimization with Pessimismcited by 7
  5. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  6. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  7. 2026Pessimism-Free Offline Learning in General-Sum Games via KL Regularizationcited by 3
  8. 2026Offline Two-Player Zero-Sum Markov Games with KL Regularizationcited by 3
  9. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
  10. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learningcited by 1
  11. 2024Trust-free Personalized Decentralized Learningcited by 0
  12. 2025Oryx: a Scalable Sequence Model for Many-Agent Coordination in Offline MARLcited by 0
4 more
  1. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  2. 2026Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representationscited by 0
  3. 2026Out-of-Distribution Generalisation with Sequence Models in Offline Multi-Agent Reinforcement Learningcited by 0
  4. 2026Inference-Time Nash Alignmentcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  2. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  3. 2024Offline Fictitious Self-Play for Competitive Games
  4. 2022Offline Equilibrium Finding
  5. 2023Offline Reinforcement Learning with Additional Covering Distributions
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps
  7. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian
  8. 2020MOReL : Model-Based Offline Reinforcement Learning