polito.it
Politecnico di Torino (logo)

Will we ever learn? - An attempt to clarify convergence of learning in games

Luca Mungo

Will we ever learn? - An attempt to clarify convergence of learning in games.

Rel. Luca Dall'Asta. Politecnico di Torino, Corso di laurea magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi), 2018

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (3MB) | Preview
Abstract:

In this work we have addressed the problem of understending which features of a game influence the convergence of a learning algorithm. Taking recent literature as a starting point we focused on the relation between the empirical convergence frequency for a given game and its best reply structure. We tried to broaden this framework and obtain more precise predictions by including quasi best replies. In order to do so, we developed an analogy between the execution of a game by two players and a diffusive process on a fully connected weighted graph. We looked at the stationary distribution of such a process and tried to see if it could be used to calibrate the strenght (e.g to infere the relative size) of each attractor.The aforementioned analogy was based on a logit one parameter (β) transformation that mapped the payoff matrix in a stochastic one. We ran exstensive simulations to see how our predictions performed as β varied. Unfortunately, the new framework seemed to give little or no improvement to the old one.Arguing that the problem was choosing the same value of β for all the games included in the simulation, we introduced the notion of optimal beta β∗ and tried to see whether this could be directly infered from the payoff matrix. To this aim, we developed and tested four different measures that were coherent with the properties of the learning algorithm. Unluckily, none of them seemed to have a clear predictive value. We finally shared some thoughts about why these methods failed and which issues they are not able to cope with.

Relators: Luca Dall'Asta
Academic year: 2017/18
Publication type: Electronic
Number of Pages: 54
Subjects:
Corso di laurea: Corso di laurea magistrale in Physics Of Complex Systems (Fisica Dei Sistemi Complessi)
Classe di laurea: New organization > Master science > LM-44 - MATHEMATICAL MODELLING FOR ENGINEERING
Ente in cotutela: INET Oxford / University of Oxford Mathematical Institute (REGNO UNITO)
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/8041
Modify record (reserved for operators) Modify record (reserved for operators)