{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/130138"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/130138","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Higher-order learning in finite games","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-08-01","abstract_has_math":false,"creators":["Toonsi, Sarah A."],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Systems & Entrepreneurial Engr","degree_department":null,"school":null,"contributors":["Shamma, Jeff S.","Basar, Tamer","Sreenivas, Ramavarapu S.","Li, Yingying"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-07-13","date_published":"2025-07-13","updated_at":"2026-07-22T22:25:06Z","subjects":["Game Theory","Control","Learning In Games"],"languages":["en","eng"],"rights":["Copyright 2025 Sarah Toonsi"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/130138","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shamma, Jeff S.","Basar, Tamer","Sreenivas, Ramavarapu S.","Li, Yingying"]},{"key":"dc:creator","label":"Author","values":["Toonsi, Sarah A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-07-13","2025-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Systems & Entrepreneurial Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Game Theory","Control","Learning In Games"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Sarah Toonsi"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/130138"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-08-01","The student, Sarah Toonsi, accepted the attached license on 2025-07-02 at 13:47.","The student, Sarah Toonsi, submitted this Dissertation for approval on 2025-07-02 at 13:50.","This Dissertation was approved for publication on 2025-07-13 at 07:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22398 on 2025-10-25 at 15:52:56","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Higher-order learning in finite games"]}]}],"canonical_facts":{"dc:contributor":["Shamma, Jeff S.","Basar, Tamer","Sreenivas, Ramavarapu S.","Li, Yingying"],"dc:creator":["Toonsi, Sarah A."],"dc:date":["2025-07-13","2025-08"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-08-01","The student, Sarah Toonsi, accepted the attached license on 2025-07-02 at 13:47.","The student, Sarah Toonsi, submitted this Dissertation for approval on 2025-07-02 at 13:50.","This Dissertation was approved for publication on 2025-07-13 at 07:52.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22398 on 2025-10-25 at 15:52:56","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/130138"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Sarah Toonsi"],"dc:subject":["Game Theory","Control","Learning In Games"],"dc:title":["Higher-order learning in finite games"],"dc:type":["text"],"thesis:degree_discipline":["Systems & Entrepreneurial Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:06Z"}