Higher-Order Uncoupled Learning Dynamics and Nash Equilibrium

A new paper by Sarah Toonsi and Jeff Shamma tackles a fundamental question in multi-agent learning: can players converge to a Nash Equilibrium (NE) without knowing each other's payoffs? The authors formalize this as higher-order uncoupled learning dynamics, where each player can maintain auxiliary states to process information but still cannot observe opponents' utilities. They establish a surprising connection between such learning and feedback stabilization in decentralized control. Their main result shows that for any finite game with an isolated completely mixed-strategy NE, there exists a higher-order uncoupled dynamic that locally drives play to that equilibrium.

However, the team also reveals a critical limitation: no single higher-order dynamic can learn every possible NE. They construct two games such that any dynamics that learn the mixed-strategy NE of one game fail to learn the NE of the other—proving a lack of universality linked to simultaneous stabilization in control theory. To impose natural constraints on learning, the authors introduce the Asymptotic Best Response (ABR) property, which requires dynamics to asymptotically play best responses to stationary environments. They show ABR relates to internal stability and provide conditions for NE compatibility. Finally, they extend the analysis to bandit settings using a higher-order replicator dynamics variant, where players only observe their own realized payoffs.