Link between evolutionary dynamics and regret minimization

Evolutionary game theory is the study of strategic interactions involving large populations of agents who base their decisions on simple, myopic rules. During the past decade, methods of evolutionary game theory have been successfully applied to describe the dynamics of learning algorithms in multi-agent settings. In this thesis, we focus on no-regret learning algorithms, since these algorithms demonstrate to be the most effective in practice. In particular, we ask whether evolutionary dynamics known so far in the literature are regret minimizers for some concept of regret. We begin by deriving the discrete version of the classical continuous-time evolutionary dynamics through a process of normalization of their respective revision protocols. Then, we extend these newly derived dynamics, allowing every agent to remember the history of previous plays and use this knowledge at every revision opportunity. Doing so, the complexity of the reasoning of an agent increases, and it allows to overcome the limitations of the single-step dynamics. Moreover, we show how, in most dynamics, regret plays an important role in the revision process. One significant result was to show that the discrete version of the Brown-von-Neumann-Nash dynamic corresponds to a well-known regret minimizer, namely Regret Matching. This finding inspired us to search for other candidate dynamics for being potential regret minimizers. We show how the Discrete Replicator Dynamic fails to minimize the overall regret in simple games while the Discrete Smith Dynamic is a promising candidate for regret minimization. Finally, we map these dynamics to games with sequential structure and derive new variations of Counterfactual Regret Minimization (CFR) using the discrete dynamics as an alternative update rule

La teoria dei giochi evolutiva e’ lo studio delle interazione strategiche tra grandi popolazioni di agenti che basano le loro decisioni su semplici regole. Nell’ultimo decennio, i metodi della teoria di gioco evolutativa sono stati applicati con successo per descrivere le dinamiche degli algoritmi di apprendimento in sistemi multiagente. In questa tesi, ci concentriamo su algoritmi di learning no-regret, dato che questi hanno dimostrato di essere i piu’ efficaci nella pratica. In particolare, ci domandiamo se le dinamiche evolutive gia’ presenti nella letteratura sono dei minimizzatori del regret, per qualche concetto di regret. Il primo passo e’ la derivazione in forma discreta delle classiche dinamiche evolutive (in forma continua) attraverso un processo di normalizzazione dei loro rispettivi protocolli di revisione. In seguito, estendiamo queste nuove dinamiche discrete, permettendo agli agenti di ricordare la storia dei turni precedenti e di usare questa conoscenza ad ogni possibilita’ di revisione. In questo modo, la complessita’ del ragionamento degli agenti aumenta e permette di superare le limitazioni delle dinamiche non estese. Inoltre, dimostriamo come in molte dinamiche il regret gioca un ruolo importante nel processo di revisione. Un risultato importante e’ stato di dimostrare come la versione discreta della dinamica di Brown-von-Neumann-Nash corrisponde esattamente ad un noto algoritmo di minimizzazione del regret, chiamato Regret matching. Questa scoperta ci ha spinto a cercare nelle altre dinamiche altri potenziali algoritmi di minimizzazione del regret. Dimostriamo, pero’, come la dinamica di replicazione non sia un buon minimizzatore mentre la dinamica Smith rappresenta un buon candidato. Infine, applichiamo usiamo queste nuove dinamiche discrete a giochi sequenziali e derivamo nuove variazioni di Counterfactual Regret Minimization (CFR).