Curriculum reinforcement learning through teleportation: the teleport MDP

Deep Reinforcement Learning (DRL) has emerged as a powerful approach for tackling complex decision-making tasks, leading to significant advancements in robotics, game-playing, and autonomous systems. Despite these successes, DRL agents still struggle to match or surpass human performance in complex domains, i.e. navigating environments with sparse rewards, high-dimensional state-action spaces, and long-term credit assignment problems remains challenging. Curriculum Learning (CL) presents a promising technique to overcome these obstacles. Inspired by the human brain's learning process, CL proposes structuring training data to gradually increase task complexity, mirroring how humans acquire knowledge by mastering simpler concepts before tackling more difficult ones. Despite empirical evidence supporting CL's effectiveness, its wider adoption has been hindered by the complexities of curriculum design and a lack of theoretical understanding. This manuscript introduces a novel framework, the Teleport Markov Decision Process (TMDP), which extends the standard MDP model by including a teleportation probability and a teleport probability distribution for sampling the next state when a teleport occurs. The teleportation probability introduces a natural ordering of task complexity: higher values correspond to simpler tasks and vice versa, converging to the original problem when the probability is zero. Therefore, modifying the teleportation probability during learning generates an implicit curriculum, effectively combining the task sequencing and generation phases. We develop theoretical foundations by adapting the Safe Policy Iteration framework to TMDPs, establishing performance guarantees and bounds on state visit distribution shifts. Building on these results, we introduce the Teleport Model Policy Iteration (TMPI) algorithm, relevant from a theoretical perspective but with limited practical applicability. We then develop two practically relevant curriculum algorithms: Static Teleport (S-T) and Dynamic Teleport (D-T). Finally, we evaluate our Teleport-based curricula in two benchmark environments, providing empirical evidence of the effectiveness of the TMDP framework.

L'Apprendimento per Rinforzo Profondo (DRL) si è affermato come un potente approccio per la risoluzione di compiti decisionali complessi, portando a notevoli progressi in campi come la robotica, i sistemi autonomi e la robotica. Nonostante la loro popolarità, gli agenti DRL riscontrano ancora difficoltà nel superare le prestazioni umane in domini complessi, ad esempio la navigazione in ambienti con elevato numero di stati e azioni, ricompense sparse e modalità particolari di attribuzione del credito a lungo termine rimane una sfida. L'Apprendimento Curricolare (CL) si presenta come un approccio promettente per affrontare queste problematiche. Ispirato al processo di apprendimento del cervello umano, il CL propone di ordinare, con un determinato criterio, i dati da sottoporre all'agente seguendo l'idea di aumentare gradualmente la complessità del compito. Ciò rispecchia il modo in cui gli esseri umani acquisiscono conoscenze, padroneggiando prima nozioni basilari per poi approcciare concetti più difficili. Nonostante le evidenze empiriche a sostegno dell'efficacia del CL, la sua applicazione è stata limitata dalle complessità di progettazione dei curricula e dalla mancanza di risultati teorici. Questo manoscritto introduce un nuovo framework, denominato Teleport Markov Decision Process (TMDP), estendendo il modello standard degli MDP con l'aggiunta di una probabilità di teletrasporto e una distribuzione di probabilità del teletrasporto, dal quale campionare lo stato successivo in caso di teletrasporto. La probabilità di teletrasporto introduce un ordinamento naturale sulla complessità dei task: valori alti corrispondono a task più semplici e viceversa, convergendo al problema originale per valori nulli. Pertanto, modificare la probabilità di teletrasporto nel corso dell'apprendimento genera un curriculum implicito, combinando di fatto le fasi di sequenziamento e generazione dei compiti. Adattando il framework definito come Safe Policy Iteration al contesto dei TMDPs, presentiamo delle basi teoriche con garanzie di miglioramento in termini di prestazioni, limitando le variazioni della distribuzione di visita degli stati. I risultati raggiunti ci consentono di introdurre l'algoritmo Teleport Model Policy Iteration (TMPI), rilevante dal punto di vista teorico, meno a livello pratico. In seguito, presentiamo due algoritmi curricolari con effettivo riscontro pratico: Static Teleport (S-T) e Dynamic Teleport (D-T). Questi ultimi possono essere utilizzati per arricchire alogoritmi di diversa natura, in ambito del RL, adattandoli ai curricula basati sul teletrasporto. Infine, valutiamo i nostri algoritmi curriculari basati sul Teletrasporto in due ambienti di riferimento, fornendo evidenze empiriche dell'efficacia del framework dei TMDPs. Ci teniamo a sottolineare che questa Tesi non si pone in alcun modo l'obiettivo di fornire una soluzione definitiva per il design di curricula efficaci ed efficienti nell'ambito del Reinforcement Learning. Al contrario, il nostro obiettivo è quello di ispirare lavori futuri a indagare più a fondo il framework proposto in modo da estenderne le proprietà e presentare delle soluzioni sempre più all'avanguardia. L'Apprendimento Curricolare (CL) si presenta come un approccio promettente per affrontare queste problematiche. Ispirato al processo di apprendimento del cervello umano, il CL propone di ordinare, con un determinato criterio, i dati da sottoporre all'agente seguendo l'idea di aumentare gradualmente la complessità del compito. Ciò rispecchia il modo in cui gli esseri umani acquisiscono conoscenze, padroneggiando prima nozioni basilari per poi approcciare concetti più difficili. Nonostante le evidenze empiriche a sostegno dell'efficacia del CL, la sua applicazione è stata limitata dalle complessità di progettazione dei curricula e dalla mancanza di risultati teorici. Questo manoscritto introduce un nuovo framework, denominato Teleport Markov Decision Process (TMDP), estendendo il modello standard degli MDP con l'aggiunta di una probabilità di teletrasporto $\tau$ e una distribuzione di probabilità del teletrasporto $\xi$, dal quale campionare lo stato successivo in caso di teletrasporto. Tale framework consente di definire un curriculum in modo implicito, combinando le fasi di sequenziamento e generazione dei compiti. La probabilità di teleporting introduce un ordinamento implicito sulla complessità dei task: valori alti corrispondono a task più semplici e viceversa, convergendo al problema originale con $\tau$ nullo. Adattando il framework definito come Safe Policy al contesto dei TMDPs, presentiamo delle basi teoriche con garanzie di miglioramento in termini di prestazioni, limitando le variazioni della distribuzione di visita degli stati. I risultati raggiunti ci consentono di introdurre l'algoritmo Teleport Model Policy Iteration (TMPI), rilevante dal punto di vista teorico, meno a livello pratico. In seguito, presentiamo due algoritmi curricolari con effettivo riscontro pratico: Static Teleport (S-T) e Dynamic Teleport (D-T). Questi ultimi possono essere utilizzati per arricchire alogoritmi di diversa natura, in ambito del RL, adattandoli ai curricula basati sul teletrasporto. Infine, valutiamo i nostri algoritmi curriculari basati sul Teletrasporto in due ambienti di riferimento, fornendo evidenze empiriche dell'efficacia del framework dei TMDPs. Ci teniamo a sottolineare che questa Tesi non si pone in alcun modo l'obiettivo di fornire una soluzione definitiva per il design di curricula efficaci ed efficienti nell'ambito del Reinforcement Learning. Al contrario, il nostro obiettivo è quello di ispirare lavori futuri a indagare più a fondo il framework proposto in modo da estenderne le proprietà e presentare delle soluzioni sempre più all'avanguardia.