Agenti autonomi per Snake tramite Reinforcement Learning tabellare: analisi e confronto di Q-Learning, SARSA e Monte Carlo

This thesis presents an analysis and comparison of tabular Reinforcement Learning algorithms — Q-Learning, SARSA, and Monte Carlo — applied to the Snake game in a fully observable 7×7 grid environment. The Reinforcement Learning framework is introduced, with particular attention to Markov Decision Processes (MDPs), contextualized within the specific case study: states, actions, transitions, and rewards are formally defined with reference to the Snake environment and subsequently applied in the various algorithms. For state representation in the tabular setting, a compact representation method based on local binary features is introduced: danger in adjacent directions, relative fruit position, current movement direction, and surrounding space accessibility. A systematic tuning phase of the reward function and hyperparameters allowed for a progressive improvement in the quality of the learned policy. The three algorithms are then systematically trained and evaluated, comparing learning curves, collected fruits, death frequency, and wins. The results show that all three approaches achieve comparable performance, with Q-Learning and SARSA being slightly more stable than Monte Carlo.

Il lavoro di tesi presenta un'analisi e confronto di algoritmi di Reinforcement Learning tabellare — Q-Learning, SARSA e Monte Carlo — applicati al gioco Snake in un ambiente completamente osservabile a griglia 7×7. Viene introdotto il framework del Reinforcement Learning, con particolare attenzione ai Markov Decision Processes (MDP), calati nel contesto specifico del caso di studio: stati, azioni, transizioni e reward vengono formalmente definiti in riferimento all'ambiente Snake e successivamente applicati nei vari algoritmi. Per la rappresentazione degli stati in ambito tabellare viene introdotto un metodo di rappresentazione compatta fondato su feature binarie locali: pericolo nelle direzioni adiacenti, posizione relativa del frutto, direzione di movimento corrente e accessibilità dello spazio circostante. Una fase di tuning sistematico della funzione di reward e degli iperparametri, ha permesso di migliorare progressivamente la qualità della policy appresa. I tre algoritmi vengono infine addestrati e valutati in modo sistematico, confrontando curve di apprendimento, frutti raccolti, frequenza di morti e vittorie. I risultati mostrano che tutti e tre gli approcci raggiungono prestazioni comparabili, con Q-Learning e SARSA leggermente più stabili rispetto a Monte Carlo.