On The Complexity Of Multi-agent Decision Making: From Learning In Games To Partial Monitoring
2023 · Dylan J. Foster, Dean P. Foster, Noah Golowich, et al.
Abstract
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 si
Authors
(none)
Tags
Stats
Related papers
- Robustness And Sample Complexity Of Model-based MARL For General-sum Markov Games (2021)0.00
- On Improving Model-free Algorithms For Decentralized Multi-agent Reinforcement Learning (2021)0.00
- Sample-efficient Reinforcement Learning Of Partially Observable Markov Games (2022)0.00
- Provably Efficient Information-directed Sampling Algorithms For Multi-agent Reinforcement Learning (2024)2.26
- Breaking The Curse Of Multiagency In Robust Multi-agent Reinforcement Learning (2024)0.00
- Incentivize Without Bonus: Provably Efficient Model-based Online Multi-agent RL For Markov Games (2025)0.00
- Understanding Individual Decision-making In Multi-agent Reinforcement Learning: A Dynamical Systems Approach (2025)0.00
- Breaking The Curse Of Multiagency: Provably Efficient Decentralized Multi-agent RL With Function Approximation (2023)0.00