Apprendimento per rinforzo: la convergenza del Q-learning

La tesi si inquadra nell'ambito dell'Intelligenza Artificiale chiamato Machine Learning (Apprendimento Automatico). Quest’ultimo si occupa dello studio, della progettazione e della realizzazione di algoritmi capaci di automatizzare la risoluzione di determinati problemi introducendo dei meccanismi che consentono a dei macchinari di migliorare, tramite l’esperienza, le proprie capacità e prestazioni nel tempo. In particolare, la tesi si focalizza sul Reinforcement Learning (Apprendimento per Rinforzo) che è l'area del Machine Learning che si occupa del processo decisionale sequenziale. Il probelma RL può essere visto come un caso particolare del problema di interazione per il raggiungimento di un obbiettivo o goal. L'entità che deve raggiungere l'obbiettivo è chiamata agente. L'entità con cui l'agente deve interagire viene denominata ambiente, che corrisponde con tutto ciò che è esterno all'agente. L'interazione agente-ambiente è continuativa, l'agente sceglie un'azione da intraprendere e in risposta l'ambiente cambia stato presentando una nuova situazione da affrontare. In particolare, l'ambiente fornisce all'agente una ricompensa. L'obbiettivo dell'agente è eseguire azioni che massimizzino la ricompensa cumulativa nel lungo periodo. In questo elaborato viene formalizzato il problema del Reinforcement Learning utilizzando il framework del processo decisionale di Markov (MPD). In particolare, viene presentato l’algoritmo Q-learning per la risoluzione di un processo decisionale di Markov finito e viene esposta la dimostrazione della convergenza di tale algoritmo a partire da risultati generali di approssimazione stocastica. Infine, nella tesi vengono analizzati anche algoritmi che estendono il Q-learning, ma sono esposti in forma euristica perché ancora non sono disponibili risultati teorici di convergenza.