A Black-box Approach For Non-stationary Multi-agent Reinforcement Learning

Abstract

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 \(\widetilde\{O\}\left(\Delta^\{1/4\}T^\{3/4\}\right)\) regret when the degree of nonstationarity, as measured by total variation \(\Delta\), is known, and \(\widetilde\{O\}\left(\Delta^\{1/5\}T^\{4/5\}\right)\) regret when \(\Delta\) is unknown, where \(T\) is the number

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyjiang2023a

Related papers

• Taming Equilibrium Bias In Risk-sensitive Multi-agent Reinforcement Learning (2024)0.00
• A Survey Of Learning In Multiagent Environments: Dealing With Non-stationarity (2017)0.00
• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
• Conservative Equilibrium Discovery In Offline Game-theoretic Multiagent Reinforcement Learning (2026)0.00
• Strategically Robust Multi-agent Reinforcement Learning With Linear Function Approximation (2026)0.00
• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• Independent Learning In Stochastic Games (2021)6.77
• Equilibrium Selection For Multi-agent Reinforcement Learning: A Unified Framework (2024)0.00