{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/124295"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/124295","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Multi-agent reinforcement learning for nonzero-sum Markov games","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms","abstract_has_math":false,"creators":["Mao, Weichao"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Başar, Tamer","Iyer, Ravishankar K.","Srikant, Rayadurgam","Raginsky, Maxim"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-05","date_published":"2024-05","updated_at":"2026-07-22T22:25:00Z","subjects":["Reinforcement Learning","Game Theory"],"languages":["en","eng"],"rights":["Copyright 2024 Weichao Mao"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/124295","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Başar, Tamer","Iyer, Ravishankar K.","Srikant, Rayadurgam","Raginsky, Maxim"]},{"key":"dc:creator","label":"Author","values":["Mao, Weichao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2024-05","2024-04-22"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer 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 at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Reinforcement Learning","Game Theory"]}]},{"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 2024 Weichao Mao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/124295"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms","The student, Weichao Mao, accepted the attached license on 2024-04-15 at 21:50.","The student, Weichao Mao, submitted this Dissertation for approval on 2024-04-15 at 22:00.","This Dissertation was approved for publication on 2024-04-22 at 16:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20427 on 2024-09-16 at 00:34:36","In recent years, multi-agent reinforcement learning (MARL) has shown remarkable capabilities in addressing sequential decision-making problems that involve the strategic interactions of more than one decision-maker. Motivated by the empirical successes, many research efforts have been devoted to lay the theoretical foundations of MARL. In this dissertation, we contribute to this line of theoretical research by developing MARL algorithms with convergence and sample complexity guarantees in nonzero-sum Markov games, a regime that has been barely touched on in prior research. First, we design sample-efficient MARL algorithms for learning (coarse) correlated equilibria in general-sum Markov games. Our algorithms integrate variants of optimistic Q-learning for efficient exploration with uncoupled no-regret learning for policy updates. These algorithms are decentralized in the sense that each agent makes decisions based on only its local information with no need of communication or central coordination. We theoretically establish the sample complexity guarantees for our algorithms, which appear to be the first for decentralized MARL in general-sum Markov games. Second, we study reinforcement learning (RL) under environmental non-stationarity, a major challenge faced by MARL agents. When both the reward functions and the state transition distributions may vary over time, we propose a simple but effective restart-based algorithm particularly tailored to such non-stationary environments. We analyze the dynamic regret of our algorithm and show that it is near-optimal by establishing an almost matching information-theoretical lower bound. We demonstrate that our non-stationary RL method can be readily applied to learning the team-optimal policies in a specific category of cooperative games with slowly-changing opponents. Third, we propose to use meta-learning to transfer useful information across multiple MARL tasks so as to learn related tasks collectively and more efficiently. We establish the first line of theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria in general-sum Markov games. Under natural notions of task similarity, we show that meta-learning achieves provable sharper convergence to various game-theoretical solution concepts than learning each task separately. Numerical results are provided to corroborate our theoretical findings. Finally, we conclude this dissertation and discuss future research directions."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Multi-agent reinforcement learning for nonzero-sum Markov games"]}]}],"canonical_facts":{"dc:contributor":["Başar, Tamer","Iyer, Ravishankar K.","Srikant, Rayadurgam","Raginsky, Maxim"],"dc:creator":["Mao, Weichao"],"dc:date":["2024-05","2024-04-22"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2024-09-16 without embargo terms","The student, Weichao Mao, accepted the attached license on 2024-04-15 at 21:50.","The student, Weichao Mao, submitted this Dissertation for approval on 2024-04-15 at 22:00.","This Dissertation was approved for publication on 2024-04-22 at 16:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #20427 on 2024-09-16 at 00:34:36","In recent years, multi-agent reinforcement learning (MARL) has shown remarkable capabilities in addressing sequential decision-making problems that involve the strategic interactions of more than one decision-maker. Motivated by the empirical successes, many research efforts have been devoted to lay the theoretical foundations of MARL. In this dissertation, we contribute to this line of theoretical research by developing MARL algorithms with convergence and sample complexity guarantees in nonzero-sum Markov games, a regime that has been barely touched on in prior research. First, we design sample-efficient MARL algorithms for learning (coarse) correlated equilibria in general-sum Markov games. Our algorithms integrate variants of optimistic Q-learning for efficient exploration with uncoupled no-regret learning for policy updates. These algorithms are decentralized in the sense that each agent makes decisions based on only its local information with no need of communication or central coordination. We theoretically establish the sample complexity guarantees for our algorithms, which appear to be the first for decentralized MARL in general-sum Markov games. Second, we study reinforcement learning (RL) under environmental non-stationarity, a major challenge faced by MARL agents. When both the reward functions and the state transition distributions may vary over time, we propose a simple but effective restart-based algorithm particularly tailored to such non-stationary environments. We analyze the dynamic regret of our algorithm and show that it is near-optimal by establishing an almost matching information-theoretical lower bound. We demonstrate that our non-stationary RL method can be readily applied to learning the team-optimal policies in a specific category of cooperative games with slowly-changing opponents. Third, we propose to use meta-learning to transfer useful information across multiple MARL tasks so as to learn related tasks collectively and more efficiently. We establish the first line of theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria in general-sum Markov games. Under natural notions of task similarity, we show that meta-learning achieves provable sharper convergence to various game-theoretical solution concepts than learning each task separately. Numerical results are provided to corroborate our theoretical findings. Finally, we conclude this dissertation and discuss future research directions."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/124295"],"dc:language":["en","eng"],"dc:rights":["Copyright 2024 Weichao Mao"],"dc:subject":["Reinforcement Learning","Game Theory"],"dc:title":["Multi-agent reinforcement learning for nonzero-sum Markov games"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:00Z"}