# On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2023.

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

- [LLMArena: Assessing Capabilities of Large Language Models in Dynamic Multi-Agent Environments](https://mlsanity.com/paper/2402.16499/) (2024)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL](https://mlsanity.com/paper/2402.05724/) (2024)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Decision Making in Hybrid Environments: A Model Aggregation Approach](https://mlsanity.com/paper/2502.05974/) (2025)
- [Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2312.04905/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2404.19292/) (2024)
- [Sample-Efficient Multi-Agent RL: An Optimization Perspective](https://mlsanity.com/paper/2310.06243/) (2023)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks](https://mlsanity.com/paper/2309.10275/) (2023)
- [A Fast Convergence Theory for Offline Decision Making](https://mlsanity.com/paper/2406.01378/) (2024)
- [State-of-the-art in Robot Learning for Multi-Robot Collaboration: A Comprehensive Survey](https://mlsanity.com/paper/2408.11822/) (2024)
- [Minimax-Optimal Policy Regret in Partially Observable Markov Games](https://mlsanity.com/paper/2606.02363/) (2026)

## Abstract (arXiv)

A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees, and how these considerations change as we move from few to many agents. We study this question in a general framework for interactive decision making with multiple agents, encompassing Markov games with function approximation and normal-form games with bandit feedback. We focus on equilibrium computation, in which a centralized learning algorithm aims to compute an equilibrium by controlling multiple agents that interact with an unknown environment. Our main contributions are: - We provide upper and lower bounds on the optimal sample complexity for multi-agent decision making based on a multi-agent generalization of the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. (2021) in the single-agent counterpart to our setting. Compared to the best results for the single-agent setting, our bounds have additional gaps. We show that no "reasonable" complexity measure can close these gaps, highlighting a striking separation between single and multiple agents. - We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making, but with hidden (unobserved) rewards, a framework that subsumes variants of the partial monitoring problem. As a consequence, we characterize the statistical complexity for hidden-reward interactive decision making to the best extent possible. Building on this development, we provide several new structural results, including 1) conditions under which the statistical complexity of multi-agent decision making can be reduced to that of single-agent, and 2) conditions under which the so-called curse of multiple agents can be avoided.