Siamo felici di annunciare che i nostri co-fondatori Alberto Marchesi e Nicola Gatti (insieme ad Andrea Celli e Gabriele Farina) hanno vinto il prestigioso Best Paper Award a NeurIPS 2020, con un lavoro su dinamiche di apprendimento no-regret in problemi di decisione sequenziali.
La Neural Information Processing Systems (NeurIPS) conference è il più importante meeting di Intelligenza Artificiale e Machine Learning, che ospita ogni anno migliaia di persone tra istituzioni accademiche e aziende di tutto il mondo. In questo anno da record, la conferenza ha avuto più di 18000 partecipanti e 9467 articoli sottomessi.
Dopo un processo di selezione estremamente selettivo, solo 1,898 articoli sono stati accettati per la pubblicazione, e tre di questi hanno anche ricevuto il prestigioso Best Paper Award per i loro contributi rivoluzionari. Alberto e Nicola hanno condiviso il premio con Open AI, per l’articolo sul loro language model GPT-3, e UC Berkeley, per un lavoro su data summarization.
Il paper vincitore “No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium” di Alberto e Nicola risolve un problema aperto da molto tempo nel campo della teoria dei giochi, informatica e economia e che avrà impatto sostanziale in scenari che prevedono la presenza di un mediatore. Nello specifico, il paper mostra che gli equilibri con un mediatore possono essere raggiunti in modo decentralizzato da agenti che agiscono in modo egoistico, anche in scenari complessi che coinvolgono decisioni sequenziali e informazione parziale.
Questo lavoro potrà avere diverse applicazioni nella gestione del traffico in modo efficiente tramite applicazioni di navigazione, nel coordinamento degli utenti in applicazioni di ride-sharing e food delivery, e nella pianificazione dell’uso di risorse condivise. Il contributo rivoluzionario dell’articolo sta nel fatto che gli agenti possono ottenere un comportamento socialmente ottimale senza l’utilizzo di un mediatore centrale, ma solo agendo in modo decentralizzato secondo l’algoritmo sviluppato nel lavoro.
Qui, l’abstract e il link al paper completo:
“The existence of simple, uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form (that is, tree-form) games generalize normal-form games by modeling both sequential and simultaneous moves, as well as private information. Because of the sequential nature and presence of partial information in the game, extensive-form correlation has significantly different properties than the normal-form counterpart, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to normal-form correlated equilibrium. However, it was currently unknown whether EFCE emerges as the result of uncoupled agent dynamics. In this paper, we give the first uncoupled no-regret dynamics that converge to the set of EFCEs in n-player general-sum extensive-form games with perfect recall. First, we introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. When each player has low trigger regret, the empirical frequency of play is close to an EFCE. Then, we give an efficient no-trigger-regret algorithm. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions at each decision point.”
link al paper “No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium”