Sample-Efficient Multi-Agent RL: An Optimization Perspective
Not on the map. Why?
Abstract (arXiv)
We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. In order to find the minimum assumption for sample-efficient learning, we introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. Using this measure, we propose the first unified algorithmic framework that ensures sample efficiency in learning Nash Equilibrium, Coarse Correlated Equilibrium, and Correlated Equilibrium for both model-based and model-free MARL problems with low MADC. We also show that our algorithm provides comparable sublinear regret to the existing works. Moreover, our algorithm combines an equilibrium-solving oracle with a single objective optimization subprocedure that solves for the regularized payoff of each deterministic joint policy, which avoids solving constrained optimization problems within data-dependent constraints (Jin et al. 2020; Wang et al. 2023) or executing sampling procedures with complex multi-objective optimization problems (Foster et al. 2023), thus being more amenable to empirical implementation.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 40 of its 56 references that are in the map. First posted on arXiv 10 Oct 2023.
Builds on
40 of 56 references.
References · 40
- 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
- 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
28 more
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
- 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
- 2017Online Reinforcement Learning in Stochastic Gamescited by 67
- 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
- 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
- 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
- 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
- 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
- 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
- 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
- 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
- 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
- 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
- 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
- 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
- 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
- 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
- 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
- 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
- 2023On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoringcited by 15
- 2022Representation Learning for General-sum Low-rank Markov Gamescited by 14
- 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
- 2022Faster No-Regret Learning Dynamics for Extensive-Form Correlated and Coarse Correlated Equilibriacited by 8
Built on by
Citing papers per year: 2024: 1.
1 paper.