Regret Minimization And Convergence To Equilibria In General-sum Markov Games

Abstract

An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Nevertheless, none of these results preclude the possibility of regret minimization under the assumption that all parties adopt the same learning procedure. In this work, we present the first (to our knowledge) algorithm for learning in general-sum Markov games that provides sublinear regret guarantees when executed by all agents. The bounds we obtain are for swap regret, and thus, along the way, imply convergence to a correlated equilibrium. Our algorithm is decentralized, computationally efficient, and does not require any communication between agents. Our key observation is that online learning via policy optimization in Markov games essentially reduces to a form of weighted regret minimization, with unknown weights determined by the path length of the agents' policy sequence. Consequently, controlling the p

Stats

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

Related papers

• Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms (2024)0.00
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Hardness Of Independent Learning And Sparse Equilibrium Computation In Markov Games (2023)0.00
• Regret Minimization In Population Network Games: Vanishing Heterogeneity And Convergence To Equilibria (2025)3.58
• Best Of Both Worlds: Regret Minimization Versus Minimax Play (2025)0.00
• Decentralized Model-free Reinforcement Learning In Stochastic Games With Average-reward Objective (2023)0.00
• \(\widetilde{o}(t^{-1})\) Convergence To (coarse) Correlated Equilibria In Full-information General-sum Markov Games (2024)0.00