mlsanityData to 7 Oct 2026

Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus

arXiv 2206.00159 ↗First posted 1 Jun 2022cs.LG cs.AI cs.GTcited by 29

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

Abstract (arXiv)

This paper considers offline multi-agent reinforcement learning. We propose the strategy-wise concentration principle which directly builds a confidence interval for the joint strategy, in contrast to the point-wise concentration principle that builds a confidence interval for each point in the joint action space. For two-player zero-sum Markov games, by exploiting the convexity of the strategy-wise bonus, we propose a computationally efficient algorithm whose sample complexity enjoys a better dependency on the number of actions than the prior methods based on the point-wise bonus. Furthermore, for offline multi-agent general-sum Markov games, based on the strategy-wise bonus and a novel surrogate function, we give the first algorithm whose sample complexity only scales sumi=1mAi where Ai is the action size of the i-th player and m is the number of players. In sharp contrast, the sample complexity of methods based on the point-wise bonus would scale with the size of the joint action space Pii=1m Ai due to the curse of multiagents. Lastly, all of our algorithms can naturally take a pre-specified strategy class Pi as input and output a strategy that is close to the best strategy in Pi. In this setting, the sample complexity only scales with log |Pi| instead of sumi=1mAi.

Key facts. Cited by 29 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 35 of its 58 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

35 of 58 references.

Closest ancestors · 11

Same direction, newest first

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  2. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  3. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning9 Jun
  7. 2021Nearly Horizon-Free Offline Reinforcement Learning25 Mar
  8. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  9. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  10. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  11. 2020Batch Value-function Approximation with Only Realizability11 Aug

Other references · 24

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  4. 2014Convex Optimization: Algorithms and Complexitycited by 569
  5. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  8. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  10. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
12 more
  1. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  2. 2021Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectificationcited by 59
  3. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  4. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  5. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  6. 2021Offline Decentralized Multi-Agent Reinforcement Learningcited by 32
  7. 2016Settling the complexity of computing approximate two-player Nash equilibriacited by 31
  8. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  9. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  10. 2020Minimax Sample Complexity for Turn-based Stochastic Gamecited by 13
  11. 2021Robustness and sample complexity of model-based MARL for general-sum Markov gamescited by 6
  12. 2021Gap-Dependent Bounds for Two-Player Markov Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

29 papers.

Sort:

By area:

  1. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  4. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  5. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  6. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  7. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  8. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  9. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  10. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  11. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  12. 2023Off-the-Grid MARL: Datasets with Baselines for Offline Multi-Agent Reinforcement Learningcited by 7
17 more
  1. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  2. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 7
  3. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  4. 2024MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Gamescited by 5
  5. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learningcited by 4
  6. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  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. 2025Rate optimal learning of equilibria from datacited by 2
  10. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1
  11. 2024Offline Fictitious Self-Play for Competitive Gamescited by 1
  12. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
  13. 2025Oryx: a Scalable Sequence Model for Many-Agent Coordination in Offline MARLcited by 0
  14. 2026Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitionscited by 0
  15. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0
  16. 2026Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representationscited by 0
  17. 2026Out-of-Distribution Generalisation with Sequence Models in Offline Multi-Agent Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  2. 2024Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization
  3. 2023A Model-Based Solution to the Offline Multi-Agent Reinforcement Learning Coordination Problem
  4. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning
  5. 2025Scalable Multi-Agent Offline Reinforcement Learning and the Role of Information
  6. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  7. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  8. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory