MDP transformation for risk averse reinforcement learning via state space augmentation

While the standard Reinforcement Learning cite{sutton2018reinforcement} objective is to minimize (maximize) the expected cumulative cost (reward) over the horizon, finite or infinite, the Risk Averse RL approach cite{surveyRiskAverse} tries to optimize not only the common objective function but involves also the minimization of what is defined as Risk. There are several ways to express the Risk of the given random cost (reward) received by the environment and the main ones are the utility functions and the proper risk measures. However, the issue in dealing with the Risk is that its minimization is not as simple as the standard optimization problem and sometimes it could become also NP-hard affecting the optimality of the found solution. The common approach historically used by the literature to find the optimal solution of this problem is based on the idea of creating new ad hoc algorithms capable to optimize the new objective function instead of the cumulative cost only. This, of course, makes the algorithm not general and specific to that kind of Risk measure or Utility function. More other, there are more standard algorithms respect to the specific ones and they are usually more studied and optimized because they are more frequently used. This is why some researchers came up with another alternative approach based on the transformation of the Markov Decision Process itself. Transforming the MDP means modifying the characteristics of the optimization problem’s formalization in terms of state space, transition kernel or Reward function to incorporate the Risk Aversion in the structure of the problem. In this way, it is possible to apply the standard Reinforcement Learning algorithms as if they are optimizing the usual objective function, while instead, they are taking into account the Risk too. The issue with this method is that we should consider how much the transformation costs in terms of computational power (and so time). Furthermore, there could be also an increment of the cost for the optimization itself after the transformation of the Markov Decision Process. In both these cases, the approach does not worth it and it would be better to adopt an ad hoc algorithm following the basic strategy for Risk-Averse optimization. My thesis deals with these problems with Risk Averse Reinforcement Learning. The idea is to modify the Markov Decision Process via a state-space augmentation that gives a piece of partial information about the history of the current chosen policy and then find the optimal solution of the modified problem through a standard Reinforcement Learning algorithm. After a proper background to present the basics needed to understand the research work, we will describe some of the interesting papers we studied about Risk Aversion and MDP transformation that gave me the idea of the state of the art in this field. Then we will explain the transformation that we decided to adopt and finally how we applied the standard RL algorithm to find the optimal Risk Sensitive policy. Finally, we will give some conclusions talking about the practical results and some possible future works in this field.

Il Reinforcement Learning è quella branca del Machine Learning che si propone di ottimizzare una certa funzione obiettivo con l'intento di massimizzare la cosiddetta "long term Reward" e quindi non focalizzandosi esclusivamente sulla Reward istantanea. Questa in generale è la definizione di Reinforcement Learning che, infatti, cerca di mimare quel tipo di processo di apprendimento umano che consiste nella ripetizione di una certa azione più e più volte, finché non se ne impara al meglio la dinamica, ovvero una politica. Questa azione deve essere orientata ovviamente a un obiettivo chiaro che, nel caso di RL, deve essere espresso come una funzione da massimizzare (o minimizzare nel caso consideriamo i costi e non le reward). L'esempio più calzante probabilmente è quello dell'addestramento di un cane (anche nell'uomo come abbiamo detto si può notare ma si riscontra meglio in obiettivi semplici e primari che sono più visibili negli animali o nei bambini piccoli). Il cane ogni volta che performa un'azione riceve dal suo padrone una ricompensa commisurata alla bontà della sua azione. Quindi se gli viene chiesto di sedersi e si siede gli verrà dato un croccantino come ricompensa così che capisca che ha eseguito l'azione in modo corretto e in futuro se ne ricorderà. L'agente si muove allo stesso modo: performerà varie azioni ricevendo Rewards di vario tipo e da essa trarrà in che direzione muoversi per massimizzarle. In questo ambito, si rende necessaria l'introduzione di un altro importante concetto per essere ancora più vicini alla replica di un' esperienza reale di apprendimento: il Rischio. Vi sono vari modi di esprimere il rischio in modo implicito o esplicito, inerente alla scolasticità dell'ambiente o alla conoscenza dell'ambiente stesso. Tutti questi approcci hanno come obiettivo comune quello di aggiungere un'informazione importante all'ottimizzazione del problema, ovvero il fatto che alcuni azioni, pur avendo possibilmente una ricompensa più alta rispetto ad altre azioni, posso essere considerate peggiori perché con il rischio di ottenere anche un ricompensa molto bassa. Infatti dobbiamo pensare all'ambiente in cui il nostro agente apprende la politica da attuare come se fosse stocastico e non ovviamente deterministico (altrimenti, la soluzione del problema il più delle volte sarebbe banale e non corrisponderebbe soprattutto alle dinamiche della Realtà in cui non tutti i fattori sono controllati dal soggetto). Questo ambito viene definito Risk-Averse Reinforcement Learning. Al riguardo, la letteratura si è mossa prevalentemente verso la definizione di algoritmi ad hoc rispetto alla misura di rischio adottata. Tuttavia, questo approccio è sconveniente perché presuppone che si trovi l’algoritmo migliore rispetto a quella certa misura di rischio, senza poi poter utilizzare gli altri algoritmi standard che vengono elaborati e ottimizzati da più ricercatori e più spesso essendo adatti all’ottimizzazione di molte più situazioni diverse e generali. Il nostro approccio si muove su questa direzione. Infatti, l'ipotesi è che possa esistere una trasformazione particolare dell’MDP (Markov Decision Process), che sarebbe la formalizzazione del problema di ottimizzazione stesso, che possa portare a ottimizzare una certa misura di rischio, senza dover modificare la struttura dell’algoritmo. In questo modo l’obiettivo è evidente: se fosse possibile, si potrebbe attuare questa modifica alla base e poi utilizzare l’algoritmo più consono per l’ottimizzazione del problema, senza doverlo modificare o addirittura derivare ex novo. La modifica che abbiamo attuato consiste nell’aumento delle spazio di stato, ovvero nell’aggiunta di un’informazione all’osservazione dello stato che, previa modifica della funzione di Reward, possa modificare la funzione che viene ottimizzata in modo però trasparente per l’algoritmo. In questa tesi, dopo un’introduzione dei concetti base fondamentali per la comprensione del lavoro di ricerca e dei lavori che in letteratura hanno affrontato il problema che abbiamo messo a tema, proporremo la nostra soluzione. Descriveremo infatti la tecnica di aumento dello stato utilizzato e spiegheremo come attuarla a livello RL, che è l’effettivo contributo portato da noi alla ricerca. Mostreremo sia a livello teorico, che a livello sperimentale la differenza tra il nostro approccio e quello della derivazione di algoritmi Policy Gradient specifici delle misure di rischio utilizzate. Negli esperimenti mostreremo in particolare la duttilità della nostra soluzione che si presta facilmente e senza sforzo aggiuntivo all’applicazione di diversi e complessi algoritmi come il Trust Region Policy Optimization (TRPO) e quindi può essere anche utilizzato in diversi ambienti.