Learning by Research

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

Algorithms running in multi-agent systems are at the core of our modern society. Recommendations on social media are managed at a global scale across different servers or even on edge devices, sensor networks coordinate with each other for environmental monitoring, automated bidding algorithms compete in online auctions, and trading bots engage in the financial markets. With the rapid advancements in artificial intelligence, the prevalence and sophistication of these multi-agent interactions are set to increase, becoming an even bigger part of our daily lives and changing many industries.

The multi-agent nature of these systems gives birth to numerous challenges that are not present in single-agent scenarios, such as coordination, competition, and managing interactions among agents with differing goals and interests. This thesis studies these challenges from a mathematical standpoint. We examine both cooperative and competitive scenarios. To account for the non-stationarity common in many of these multi-agent systems, we base our approach on the online learning framework and propose new gradient-based learning algorithms with favorable theoretical guarantees. Specifically, these algorithms typically achieve "low regret" in various scenarios, meaning they cannot perform much worse than the baseline of always taking the best fixed action over the time horizon. In competitive scenarios, we also demonstrate the stability of our algorithms by proving convergence to Nash equilibrium, given the underlying game satisfies a certain "variational stability" assumption.

Additionally, we address two separate challenges: delays and stochastic feedback, respectively in the cooperative and competitive scenarios, both of which are prevalent in multi-agent systems. Our algorithms are designed to be adaptive, enabling them to operate with local information available to each agent at each time instant, and achieve different favorable guarantees automatically with a single algorithm. These factors together pose significant challenges both to the conception of the algorithms and their analysis, which are at the heart of this thesis.

Mots clés : Distributed artificial intelligence, game theory, multi-agent, online learning, learning in games, delay, adadptivity, uncertainty

Doctoral School: ED MSTII - Mathematics and Informatics
Research laboratory: Laboratoire Jean Kuntzmann (LJK - CNRS, Inria, Grenoble INP-UGA, UGA) 
Thesis supervision: Jérôme MALICK, Panayotis MERTIKOPOULOS and Franck LUTZELER

> To find out about all the 2024 thesis prizes