Decision-Making in multi-agent systems: delays, adaptivity, and learning in games

français

Speciality : Mathématiques et Informatique

7/11/2023 - 14:00 Yu-Guan Hsieh (Université Grenoble Alpes) IMAG Salle séminaire 1

Keywords :
  • decentralized
  • delay
  • uncertainty
  • adaptivity
  • learning in games
With the increasing deployment of decision-making and learning algorithms in multi-agent systems, it becomes imperative to understand their efficiency and improve their performance.The design and analysis of these systems, however, confront significant challenges. These range from practical implementation issues to the intrinsic complexity of multi-agent dynamics, where agent interactions can be cooperative, competitive, or a mix of the two. On top of this is the presence of non-stationarity, driven by either the unpredictable character of nature or interaction with other strategic entities.

This thesis represents a targeted attempt to navigate this complex landscape, investigating separately two critical aspects: the impact of delays and the interactions among agents with non-aligned interests. This dual focus is due to the relevance of these issues to practical deployment and the inherent difficulty of learning in such systems, aiming to reveal fundamental insights about how information flow and strategic interactions influence the overall system's learning and decision-making processes. Our approaches are grounded in decentralized optimization and game theory, using online learning as a principal methodology to address the non-stationarity of the environment.

More precisely, we delve into the study of a dual averaging algorithm in an asynchronous, delayed cooperative online learning setting, introducing concepts like virtual iterates and faithful permutations for its regret analysis. As for the non-cooperative setup, we investigate agents' convergence to Nash equlibrium and their individual performance guarantees when using optimistic algorithms that integrate a lookahead step. Central to our approaches is the adaptivity of the algorithms and their capability to handle uncertainties during agent interactions, operating seamlessly even in environments where agents lack knowledge or coordination. In light of these developments, we aspire to offer adaptive guarantees that remain robust amidst dynamic, uncertain environments.

----
The defense will also be broadcast via zoom
Zoom link: https://univ-grenoble-alpes-fr.zoom.us/j/98673879161?pwd=ekpDYUN1TGRwNm5EU2ZsczE4dms1QT09
Meeting ID: 986 7387 9161
Passcode: 924372

President:

Professor Anatoli Juditsky (Université Grenoble Alpes)

Directors:

  • DR Jérôme Malick (CNRS & Université Grenoble Alpes )
  • Professor Franck Iutzeler (Université Toulouse III - Paul Sabatier )
  • CR Panayotis Mertikopoulos (CNRS & Université Grenoble Alpes )

Raporteurs:

  • Professor Constantinos Daskalakis (MIT )
  • Éméritat Sylvain Sorin (Sorbonne Université )

Examinators:

  • Professor Nicolò Cesa-Bianchi (Università degli Studi di Milano )
  • DR Alexandre d'Aspremont (CNRS & École Normale Supérieure )
  • Professor Maryam Kamgarpour (EPFL )