A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
We investigate learning the equilibria in non-stationary multi-agent systems and address the challenges that differentiate multi-agent learning from single-agent learning. Specifically, we focus on games with bandit feedback, where testing an equilibrium can result in substantial regret even when the gap to be tested is small, and the existence of multiple optimal solutions (equilibria) in stationary games poses extra challenges. To overcome these obstacles, we propose a versatile black-box approach applicable to a broad spectrum of problems, such as general-sum games, potential games, and Markov games, when equipped with appropriate learning and testing oracles for stationary environments. Our algorithms can achieve widetildeOleft(Delta1/4T3/4right) regret when the degree of nonstationarity, as measured by total variation Delta, is known, and widetildeOleft(Delta1/5T4/5right) regret when Delta is unknown, where T is the number of rounds. Meanwhile, our algorithm inherits the favorable dependence on number of agents from the oracles. As a side contribution that may be independent of interest, we show how to test for various types of equilibria by a black-box reduction to single-agent learning, which includes Nash equilibria, correlated equilibria, and coarse correlated equilibria.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 24 of its 47 references that are in the map. First posted on arXiv 12 Jun 2023.
Builds on
24 of 47 references.
References · 24
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
- 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
- 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
- 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
- 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
- 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 57
- 2021A Simple Approach for Non-stationary Linear Banditscited by 54
- 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 49
12 more
- 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
- 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
- 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
- 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
- 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 27
- 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 27
- 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
- 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
- 2018Multi-agent online learning in time-varying gamescited by 17
- 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
- 2022Learning in Congestion Games with Bandit Feedbackcited by 10
- 2022Sample-Efficient Learning of Correlated Equilibria in Extensive-Form Gamescited by 7
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 2.
3 papers.