New Equilibrium Concept for AI Agents Learning via Mirror Descent

Joshua Steier's new paper, "Ergodic Deviation-Robust Equilibrium under Mirror Descent Learning in Finite Games," introduces a dynamics-relative equilibrium concept called EDRE for repeated games where agents learn via entropic mirror descent (EMD). EDRE tightly couples three requirements: (1) the limit profile is an ε-Nash equilibrium at a product distribution, (2) along the entire trajectory, every fixed coalition's cumulative unilateral deviation gain is Õ(√T) with high probability, and (3) the limit profile is a fixed point of the EMD map—ensuring it is actually selected by the dynamics, not just certified statically. The paper proves the √T deviation-regret rate is order-tight and establishes existence in exact-potential games using Nash's theorem and constructive proximal routes. It also extends the selection property to monotone polymatrix games through variational inequalities.

On the complexity side, Steier shows that computing EDRE is PPAD-hard in general polymatrix games but belongs to promise-PPAD for potential games. The work includes a worked 2×2 coordination example and several extensions: a bandit-feedback variant, a period-doubling route to Li-Yorke chaos for two-strategy EMD maps at large step sizes, and a linear-program formulation for minimum-cost steering. While a static EDRE coincides with ε-Nash, its real value lies in dynamic certification—excluding linearly unstable equilibria. This research bridges game theory and online learning, offering a robust stability certificate for multi-agent AI systems.