L'apprendimento per rinforzo per il problema del massimo insieme indipendente pesato

During the last few years some attempts have been made to solve combinatorial optimization problems using reinforcement learning. In these work we review these attempts for the maximum weighted independent set problem and we analyze their issues. In particular we notice that the simmetry of the problem makes it necessary to implement some sort of differentiation of the proposed solutions, we try to tackle this issue with Stein variational gradient descend, an algorithm from bayesian statistics.

Negli ultimi anni sono stati fatti dei tentativi di risolvere il problema del massimo insieme indipendente pesato con metodi di reinforcement learning. In questa tesi analizziamo questi tentativi e i problemi che presentano. In particolare osserviamo come la simmetria del problema rende necessario un qualche tipo di differenziazione delle soluzioni, proviamo ad affrontare il problema utilizzando un algoritmo di statistica bayesiana: lo Stein variational gradient descend,