Reward-free policy space compression for learning in Markov decision processes

A Markov decision process is a widespread mathematical framework to formalize sequential decision-making problems. In this context, an artificial learning agent interacts with a potentially unknown environment, aiming to reach a previously defined long-term goal. Usually, the performance of the agent is evaluated through a reward function: a numerical feedback that indicates to the agent how well it is performing with respect to its task. Solving a Markov decision process means finding an interaction strategy that maximizes the cumulative sum of rewards, commonly called optimal policy. To find such a policy, a suitable way is to explore the set of all the strategies, looking for an optimal one. Unfortunately, because of the enormous size of the policy space and its complex relation with the environment dynamics, performing this search is an arduous challenge. The goal of this thesis is to devise a method to substantially ease the policy search problem, by performing a compression of the policy space into a finite set of representative elements. These elements are representative in the sense that, via off-policy estimation techniques, they allow to approximately evaluate the performance of any policy. In this document we propose and analyze a viable solution procedure to such problem, and we consequently evaluate the compression quality with some practical examples. Moreover, we provide theoretical guarantees on the obtained results and we suggest interesting directions for future works.

Il processo decisionale di Markov è una struttura matematica utilizzata per formalizzare problemi decisionali sequenziali. In questo contesto, un agente di apprendimento artificiale interagisce con un ambiente potenzialmente sconosciuto, mirando a raggiungere un obiettivo a lungo termine precedentemente definito. Di solito, le prestazioni dell'agente sono valutate attraverso una funzione di ricompensa: un riscontro numerico che indica all'agente quanto bene stia eseguendo il suo compito. Risolvere un processo decisionale di Markov significa trovare una strategia di interazione che massimizzi la somma delle ricompense, comunemente chiamata politica ottimale. Per trovare tale politica, una possibilità è esplorare l'insieme di tutte le strategie, cercandone una ottimale. Sfortunatamente, a causa dell'enorme dimensione dello spazio delle politiche e della sua complessa relazione con la dinamica dell'ambiente, eseguire tale ricerca è un’ardua sfida. L'obiettivo di questa tesi è ideare un metodo per facilitare sostanzialmente la ricerca delle strategie ottimali, eseguendo una compressione dello spazio delle politiche in un insieme finito di elementi rappresentativi. Questi elementi sono rappresentativi nel senso che, attraverso tecniche di stima off-policy, permettono di valutare approssimativamente le prestazioni di qualsiasi politica. In questo documento proponiamo e analizziamo un algoritmo adatto a risolvere questo problema, e conseguentemente valutiamo la qualità della compressione con alcuni esempi pratici. Inoltre forniamo garanzie teoriche sui risultati ottenuti e suggeriamo interessanti spunti per lavori futuri.