Higher-order learning in finite games

Toonsi, Sarah A.

Permalink

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

Description

Title

Higher-order learning in finite games

Author(s)

Toonsi, Sarah A.

Issue Date

2025-07-13

Director of Research (if dissertation) or Advisor (if thesis)

Shamma, Jeff S.

Doctoral Committee Chair(s)

Shamma, Jeff S.

Committee Member(s)

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

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Systems & Entrepreneurial Engr

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Game Theory
• Control
• Learning In Games

Language

eng

Abstract

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.

Graduation Semester

2025-08

Type of Resource

Text

Handle URL

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

Copyright and License Information

Copyright 2025 Sarah Toonsi

Owning Collections