Higher-order learning in finite games

This work aims to contribute to the understanding of multi-agent learning. We adopt the approach of modeling agents as game-theoretic learners who adapt their strategies over time. The learning problem is formulated as a dynamical system that evolves in response to external stimuli. From this perspective, we employ tools and concepts from feedback and control theory to analyze these systems. The focus is on uncoupled higher-order learning dynamics, with a special emphasis on the learnability of the game-theoretic solution concept known as mixed-strategy Nash Equilibrium (NE). In uncoupled dynamics, a player's dynamics do not depend explicitly on the utility functions of other players. Most traditional analyses focus on standard-order learning dynamics, which restrict the dimensionality of a player’s learning dynamics to match the dimensionality of their strategy space. In contrast, higher-order learning lifts this constraint by augmenting a player's dynamics with auxiliary states that can capture complex phenomena such as path dependencies. Relevant analogies in this regard include optimization schemes that use memory, such as optimistic variants of gradient ascent. Previous studies attributed the impossibility of learning mixed-strategy NE to the natural requirement that the dynamics are uncoupled. However, recent studies have shown that higher-order learning dynamics can overcome such a limitation. A general understanding of what is achievable with higher-order learning remains an open problem. This work addresses the problem of learning isolated completely mixed-strategy NE in finite games using uncoupled higher-order learning dynamics. First, we prove learnability of isolated completely mixed-strategy NE under different uncoupled information schemes. We achieve this result by linking uncoupled learning to the concept of "decentralized feedback stabilization." Specifically, we show that for any finite game with an isolated completely mixed-strategy NE, there exist higher-order uncoupled learning dynamics that can (locally) lead to that NE, both for the specific game and nearby games with perturbed utility functions. Furthermore, we use the ODE method of stochastic approximation to extend continuous-time learnability results to a stochastic discrete-time setup where players can only observe instantaneously realized utilities. A key insight is that learning limitations arise not only from incomplete knowledge of the game (uncoupled dynamics) but also from computational constraints faced by the players (standard-order dynamics). We then explore limitations of higher-order learning. In particular, we consider the problem of non-universal convergence, i.e., no dynamics can lead to NE in all games. In this regard, we present two approaches, each relying on a control-theoretic concept. The first approach employs root-locus analysis, while the second utilizes the idea of simultaneous stabilization. After discussing learnability and limitations, we address the problem of "natural" higher-order constructions. We introduce the Asymptotic Best-Response property of natural dynamics. We link this concept to the internal stability of the higher-order components and use the ``parity interlacing principle" from control theory to discuss how certain mixed-strategy NE are incompatible with natural behavior. Finally, we conclude with a discussion of the broader relevance of this work and outline potential directions for future research.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Systems & Entrepreneurial Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Toonsi, Sarah A.

Contributors dc:contributor

• Shamma, Jeff S.
• Basar, Tamer
• Sreenivas, Ramavarapu S.
• Li, Yingying

• Game Theory
• Control
• Learning In Games

Statement dc:rights

• Copyright 2025 Sarah Toonsi

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/130138

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F130138