mlsanityData to 14 Oct 2026

Sample-Efficient Reinforcement Learning of Partially Observable Markov Games

arXiv 2206.01315 ↗First posted 2 Jun 2022cs.LG cs.AI cs.GTcited by 27

Not on the map. Why?

Abstract (arXiv)

This paper considers the challenging tasks of Multi-Agent Reinforcement Learning (MARL) under partial observability, where each agent only sees her own individual observations and actions that reveal incomplete information about the underlying state of system. This paper studies these tasks under the general model of multiplayer general-sum Partially Observable Markov Games (POMGs), which is significantly larger than the standard model of Imperfect Information Extensive-Form Games (IIEFGs). We identify a rich subclass of POMGs -- weakly revealing POMGs -- in which sample-efficient learning is tractable. In the self-play setting, we prove that a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to find approximate Nash equilibria, correlated equilibria, as well as coarse correlated equilibria of weakly revealing POMGs, in a polynomial number of samples when the number of agents is small. In the setting of playing against adversarial opponents, we show that a variant of our optimistic MLE algorithm is capable of achieving sublinear regret when being compared against the optimal maximin policies. To our best knowledge, this work provides the first line of sample-efficient results for learning POMGs.

Key facts. Cited by 27 papers in the map (data through 14 Oct 2026). Builds on 29 of its 60 references that are in the map. First posted on arXiv 2 Jun 2022.

Builds on

29 of 60 references.

References · 29

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  10. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  11. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  12. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
17 more
  1. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  2. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  3. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  4. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  5. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  6. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  7. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 57
  8. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  9. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
  10. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  11. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  12. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  13. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  14. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  15. 2021Model-Free Online Learning in Unknown Sequential Decision Making Problems and Gamescited by 12
  16. 2017Learning for Multi-robot Cooperation in Partially Observable Stochastic Environments with Macro-actionscited by 8
  17. 2015Timeability of Extensive-Form Gamescited by 7

Built on by

Cited by year (2026 to 14 Oct)

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

27 papers.

Sort:

By area:

  1. 2023Is RLHF More Difficult than Standard RL?cited by 96
  2. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  3. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  4. 2024AdaSociety: An Adaptive Environment with Social Structures for Multi-Agent Decision-Makingcited by 20
  5. 2025Training Language Models for Social Deduction with Multi-Agent Reinforcement Learningcited by 16
  6. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  7. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 14
  8. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 8
  9. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  10. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  11. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
  12. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
15 more
  1. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  2. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  3. 2025Causality-informed Anomaly Detection in Partially Observable Sensor Networks: Moving beyond Correlationscited by 2
  4. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  5. 2025A Roadmap Towards Improving Multi-Agent Reinforcement Learning With Causal Discovery And Inferencecited by 1
  6. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamicscited by 1
  7. 2024Lyapunov-based reinforcement learning for distributed control with stability guaranteecited by 0
  8. 2025The Fair Game: Auditing & Debiasing AI Algorithms Over Timecited by 0
  9. 2025Co-Evolving Complexity: An Adversarial Framework for Automatic MARL Curriculacited by 0
  10. 2026Cooperative Multi-agent RL with Communication Constraintscited by 0
  11. 2026Internal State-Based Policy Gradient Methods for Partially Observable Markov Potential Gamescited by 0
  12. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0
  13. 2026The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processescited by 0
  14. 2026A Unified Causal-Origin Taxonomy of Distributional Shifts in Reinforcement Learningcited by 0
  15. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0