Hardness Of Independent Learning And Sparse Equilibrium Computation In Markov Games

Abstract

We consider the problem of decentralized multi-agent reinforcement learning in Markov games. A fundamental question is whether there exist algorithms that, when adopted by all agents and run independently in a decentralized fashion, lead to no-regret for each player, analogous to celebrated convergence results in normal-form games. While recent work has shown that such algorithms exist for restricted settings (notably, when regret is defined with respect to deviations to Markovian policies), the question of whether independent no-regret learning can be achieved in the standard Markov game framework was open. We provide a decisive negative resolution this problem, both from a computational and statistical perspective. We show that: - Under the widely-believed assumption that PPAD-hard problems cannot be solved in polynomial time, there is no polynomial-time algorithm that attains no-regret in general-sum Markov games when executed independently by all players, even when the game is kn

Stats

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

Related papers

• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Independent Learning In Constrained Markov Potential Games (2024)0.00
• On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games (2023)0.00
• Provably Efficient Reinforcement Learning In Decentralized General-sum Markov Games (2021)0.00
• Independent And Decentralized Learning In Markov Potential Games (2022)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms (2024)0.00
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00