Efficiently Computing Nash Equilibria In Adversarial Team Markov Games

Abstract

Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, provable guarantees have been thus far either limited to fully competitive or cooperative scenarios or impose strong assumptions that are difficult to meet in most practical applications. In this work, we depart from those prior results by investigating infinite-horizon *adversarial team Markov games*, a natural and well-motivated class of games in which a team of identically-interested players -- in the absence of any explicit coordination or communication -- is competing against an adversarial player. This setting allows for a unifying treatment of zero-sum Markov games and Markov potential games, and serves as a step to model more realistic strategic interactions that feature both competing and cooperative interests. Our main contribution is the first algorithm for computing stationary \(\epsilon\)-approximate N

Stats

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

Related papers

• Learning Equilibria In Adversarial Team Markov Games: A Nonconvex-hidden-concave Min-max Optimization Problem (2024)0.00
• Empirical Policy Optimization For \(n\)-player Markov Games (2021)0.00
• Policy Optimization For Markov Games: Unified Framework And Faster Convergence (2022)0.00
• Can We Find Nash Equilibria At A Linear Rate In Markov Games? (2023)0.00
• Learning Equilibria From Data: Provably Efficient Multi-agent Imitation Learning (2025)0.00
• Strategically Robust Multi-agent Reinforcement Learning With Linear Function Approximation (2026)0.00
• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
• A Sharp Analysis Of Model-based Reinforcement Learning With Self-play (2020)0.00