A Geometric Study on Policy Space Compression

In the last decades, reinforcement learning emerged as a powerful tool to address sequential decision making under uncertainty, counting a number of success stories ranging from game solving, to robotic manipulation, and text generation. However, to achieve those impressive breakthroughs, the reinforcement learning algorithms require to be trained on a massive number of samples collected from the environment, which limits the applicability of these techniques to a broader set of real-world problems. A significant source of this samples inefficiency is due to the size of the so-called policy space, i.e., the set of decision strategies from which to learn the one to be deployed. Critically, the more choices of decision strategies we have, the more we can expect to achieve a desirable performance, but the less efficient will the learning process be. A recent work by~\citet{mutti2022reward} addresses the endemic sample inefficiency of reinforcement learning trying to compress the set of decision strategies as a pre-processing. The goal of this process, which is called policy space compression, is to reduce the size of the policy space by retaining most of its expressive power, so that a small dip in the performance reinforcement learning can achieve is compensated by improved efficiency. Practically, policy space compression tries to find a (small) set of $K$ representative policies that covers the set of state-action distributions induced by all the policies in the original policy space, where the covering is approximated with a covering threshold $\sigma$. While an algorithm for policy space compression is also presented in~\cite{mutti2022reward}, the original paper leaves some important questions open. In this thesis, we provide a geometric study of the policy space compression problem to provide answers to two pressing questions: How to properly set the covering threshold $\sigma$ and the number of covering policies $K$. First, we provide a study on the value of $\sigma$, showing that setting $\sigma$ to be equal to the number of state-action pairs, the default choice in the previous work, can admit a trivial solution that defeats the purpose of the compression under certain conditions. Then, we provide a more meaningful range of $\sigma$ that is better aligned with the ultimate goal of policy space compression. Finally, we present computationally tractable algorithms to check whether a tentative compression satisfies the desired covering threshold or not. In a second part of the dissertation, we instead provide lower and upper bounds on the number of representative policies $K$ that are needed to solve the policy space compression. The derived bounds have a direct dependence with the covering threshold $\sigma$ as well as all the main parameters of the problem. To conclude, we hope that this thesis will provide a critical advancement in the understanding of the policy space compression problem, fostering its applicability to a wide set of real-world applications.

Negli ultimi anni le tecniche di apprendimento per rinforzo sono emerse come importante strumento per risolvere problemi di decisione sequenziali nell’ambito dell’intelligenza ar- tificiale. In particolare, l’apprendimento per rinforzo ha portato una serie di successi in giochi strategici, robotica e generazione di testo. Tuttavia, per raggiungere questi suc- cessi, gli algoritmi di apprendimento per rinforzo richiedono di essere addestrati su una gigantesca mole di dati, limitandone l’applicazione ad una più ampia classe di problemi. Una delle principali sorgenti di questa inefficienza nell’utilizzo dei dati è da imputare alla dimensione dello spazio delle politiche, ovvero dell’insieme di strategie di decisione da cui estrarre la strategia migliore. Chiaramente, più grande è lo spazio delle politiche, maggiore è la performance che possiamo aspettarci dalla strategia ottima, ma trovare quest’ultima strategia risulterà più inefficiente. Un articolo recente di Mutti et al. [12] ha proposto di attaccare il problema di inefficienza dell’apprendimento del rinforzo cercando di comprimere lo spazio delle politiche come pre-processing. L’obiettivo di questo pre-processing. che viene chiamato compressione dello spazio delle politiche, è quello di ridurre la dimensione dello spazio delle politiche mantenendo la maggior aprte del suo potere espressivo, così che un fisiologico calo nella performance raggiunta dall’apprendimento per rinforzo è compensata da una migliore efficienza. In pratica, la comrpessione dello spazio delle politiche cerca di identificare un (possibilmente piccolo) insieme di K politiche rappresentative che copre tutte le dis- tribuzioni su stati-azioni indotte dalle politiche dello spazio originale, dove la copertura è approssimata con una soglia di copertura σ. L’articolo originale propone un algoritmo per la compressione dello spazio delle politiche, ma lascia aperte alcune imporanti domande. Questa tesi fornisce uno studio geometrico del problema di compressione dello spazio delle politiche per rispondere a due importanti domande: come scegliere la soglia di copertura σ e il numero di politiche rappresentative K. Innanzitutto, la tesi studia il valore di σ, mostrando che scegleire un valore uguale al numero delle coppie stato-azione, scelta standard del lavoro precedente, potrebbe am- mettere una soluzione banale che mina l’utilità della compressione dello spazio delle politiche. Quindi proponiamo un più significativo range di valori σ che meglio si allinea con l’obiettivo della compressione. Infine, presentiamo un insieme di algoritmi trattabili per verificare se un tentativo di compressione soddisfa la soglia σ desiderata oppure no. In una seconda parte del contributo, la tesi fornisce estermi inferiori e superiori sul numero di politiche K che è necessario per risolvere il problema di compressione. Le relazioni in questione hanno una dipendenza diretta con la soglia σ e le quantità più rilevanti del problema. In conclusione, speriamo che questa tesi possa fornire un avanzamento cruciale nella com- presione del problema di compressione dello spazio delle politiche, così da permetterne la sua applicazione ad una vasta classe di problemi.