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

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

## Key facts

- Cited by 30 papers in the map (data through 14 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.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 30 of 35)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification](https://mlsanity.com/paper/2111.11188/) (2021)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets](https://mlsanity.com/paper/2202.07511/) (2022)
- [Towards General Function Approximation in Zero-Sum Markov Games](https://mlsanity.com/paper/2107.14702/) (2021)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [Offline Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2108.01832/) (2021)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)

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

- [REBEL: Reinforcement Learning via Regressing Relative Rewards](https://mlsanity.com/paper/2404.16767/) (2024)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [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 Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [Beyond Pessimism: Offline Learning in KL-regularized Games](https://mlsanity.com/paper/2604.06738/) (2026)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Off-the-Grid MARL: Datasets with Baselines for Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2302.00521/) (2023)
- [A Reduction-based Framework for Sequential Decision Making with Delayed Feedback](https://mlsanity.com/paper/2302.01477/) (2023)
- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Offline Two-Player Zero-Sum Markov Games with KL Regularization](https://mlsanity.com/paper/2605.13025/) (2026)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)
- [Pessimism-Free Offline Learning in General-Sum Games via KL Regularization](https://mlsanity.com/paper/2605.00264/) (2026)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [Rate optimal learning of equilibria from data](https://mlsanity.com/paper/2510.09325/) (2025)
- [Offline congestion games: How feedback type affects data coverage requirement](https://mlsanity.com/paper/2210.13396/) (2022)
- [Offline Fictitious Self-Play for Competitive Games](https://mlsanity.com/paper/2403.00841/) (2024)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Oryx: a Scalable Sequence Model for Many-Agent Coordination in Offline MARL](https://mlsanity.com/paper/2505.22151/) (2025)
- [Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions](https://mlsanity.com/paper/2602.14321/) (2026)
- [Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback](https://mlsanity.com/paper/2603.28281/) (2026)
- [Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representations](https://mlsanity.com/paper/2609.02928/) (2026)
- [Out-of-Distribution Generalisation with Sequence Models in Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2609.03667/) (2026)
- [Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage](https://mlsanity.com/paper/2610.04997/) (2026)

## 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.