On The Complexity Of Computing Sparse Equilibria And Lower Bounds For No-regret Learning In Games

Abstract

Characterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have revealed that when all players adopt specific learning algorithms, it is possible to improve exponentially over what is predicted by the overly pessimistic no-regret framework in the traditional adversarial regime, thereby leading to faster convergence to the set of coarse correlated equilibria (CCE). Yet, despite considerable recent progress, the fundamental complexity barriers for learning in normal- and extensive-form games are poorly understood. In this paper, we make a step towards closing this gap by first showing that -- barring major complexity breakthroughs -- any polynomial-time learning algorithms in extensive-form games need at least \(2^\{log^\{1/2 - o(1)\} |\mathcal\{T\}|\}\) iterations for the average regret to reach below even an absolute constant, where \(|\mathcal\{T\}|\) is the number of nodes in

Stats

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

Related papers

• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Hardness Of Independent Learning And Sparse Equilibrium Computation In Markov Games (2023)0.00
• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Simple Uncoupled No-regret Learning Dynamics For Extensive-form Correlated Equilibrium (2021)6.34
• Uncoupled Learning Dynamics With \(o(\log T)\) Swap Regret In Multiplayer Games (2022)0.00
• On The Impossibility Of Convergence Of Mixed Strategies With No Regret Learning (2020)0.00
• \(\widetilde{o}(t^{-1})\) Convergence To (coarse) Correlated Equilibria In Full-information General-sum Markov Games (2024)0.00