Exploiting structure for transfer in reinforcement learning

Recent advancements have allowed reinforcement learning algorithms to achieve outstanding results in a variety of complex sequential decision-making problems, from playing board and video games to the control of sophisticated robotic systems. However, current techniques are still very inefficient, in the sense that they require a huge amount of experience before learning near-optimal behavior. One solution to mitigate this limitation is knowledge transfer, i.e., the process of reusing experience obtained while facing previous tasks to speed-up the learning process of new related problems. In this thesis, we offer a number of contributions to the field of transfer in reinforcement learning, from practical to theoretical aspects. We do so in the context of structured domains, a concept that we introduce to model problems with similarities that enable knowledge transfer. We start by studying how to reuse old experience from a set of source tasks to reduce the sample complexity for learning a target task. For this problem, we derive two novel algorithms for batch and online settings, respectively. We then study the problem of generating new experience, i.e., of exploration in the target task given knowledge from previous tasks. We first design a practical algorithm that explores the target task driven by a prior distribution over its solution that is learned from the source tasks. We then study this problem from a theoretical perspective under the assumption that the underlying task structure, or an approximation of it, is known. For both multi-armed bandits and Markov decision processes, we design different algorithms for which we formally establish the benefits of exploiting structure, while ensuring optimality in specific cases. All together, these results advance our understanding of knowledge transfer, one of the key components towards the deployment of reinforcement learning agents to the real world.

I recenti progressi hanno consentito agli algoritmi di apprendimento per rinforzo di ottenere risultati eccezionali in vari complessi problemi di decisione sequenziale, dai giochi da tavolo e videogiochi al controllo di sofisticati sistemi robotici. Tuttavia, le tecniche attuali sono ancora molto inefficienti, nel senso che richiedono un'enorme quantità di esperienza prima di apprendere un comportamento quasi ottimale. Una soluzione per mitigare questa limitazione è il trasferimento della conoscenza, ovvero il processo di riutilizzo dell'esperienza ottenuta risolvendo compiti precedenti per accelerare il processo di apprendimento di nuovi problemi correlati. In questa tesi, offriamo una serie di contributi al campo del trasferimento nell'apprendimento per rinforzo, dagli aspetti pratici a quelli teorici. Lo facciamo nel contesto dei domini strutturati, un concetto che introduciamo per modellare problemi con similarità che consentono il trasferimento di conoscenza. Iniziamo studiando come riutilizzare la vecchia esperienza da un insieme di problemi sorgente per ridurre la complessità campionaria per l'apprendimento di un problema finale. Per questa problematica, deriviamo due nuovi algoritmi rispettivamente per i contesti batch e online. Studiamo quindi il problema della generazione di nuova esperienza, cioè dell'esplorazione nel problema finale data la conoscenza acquisita dai problemi precedenti. Per prima cosa progettiamo un algoritmo pratico che esplora l'ambiente finale guidato da una distribuzione a priori sulla sua soluzione che viene appresa dai problemi di origine. Studiamo quindi questo problema da una prospettiva teorica assumendo che la struttura sottostante, o un'approssimazione di essa, sia nota. Sia per i banditi multi-armati che per i processi decisionali di Markov, progettiamo diversi algoritmi per i quali stabiliamo formalmente i vantaggi della struttura utilizzata, garantendo al contempo l'ottimalità in casi specifici. Tutti insieme, questi risultati fanno avanzare la nostra comprensione del trasferimento di conoscenza, una delle componenti chiave per il dispiegamento di agenti di apprendimento per rinforzo nel mondo reale.