Stochastic variance reduced policy gradient

In this composition, we propose a novel Reinforcement Learning (RL) algorithm consisting in a stochastic variance-reduced version of policy gradient to solve Markov Decision Processes (MDPs). Stochastic Variance Reduced Gradient (SVRG) methods have proven to be very successful in supervised learning. However, their adaptation to policy gradient is not straightforward and needs to account for I) a non-concave objective function; II) approximations in the Full Gradient (FG) computation; and III) a non-stationary sampling process. The result is Stochastic Variance Reduced Policy Gradient (SVRPG), a stochastic variance reduced policy gradient algorithm that leverages on importance weights to preserve the unbiasedness of the gradient estimate. Under standard assumptions on the MDP, we provide convergence guarantees for SVRPG with a convergence rate that is linear under increasing batch sizes. Finally, we suggest practical variants of SVRPG, and we empirically evaluate them on continuous MDPs.

In questo elaborato proponiamo un nuovo algoritmo di Reinforcement Learning (RL). Questo algoritmo, consiste nell’utilizzo di una tecnica chiamata SVRG volta alla riduzione della varianza dello stimatore utilizzato dal policy gradient nella risoluzione di processi decisionali di Markov (MDPs). Algoritmi quali SVRG hanno avuto molto successo nell’ambito dell’ apprendimento supervisionato. Il suo utilizzo in contesti policy gradient non è banale e necessita di tenere in considerazione alcune cose: I) la funzione obiettivo non concava; II) il FG deve essere necessariamente approssimato; III) il processo di campionamento non è stazionario. Il risultato è SVRPG, un algoritmo di riduzione della varianza del gradiente della politica che sfrutta gli importance weights per preservare la correttezza dello stimatore del gradiente stesso. Date le classiche assunzioni del MDP, abbiamo fornito garanzie di convergenza per SVRPG con un tasso di convergenza che è lineare al crescere della dimensione del batch. Infine abbiamo implementato una variante pratica di SVRPG. Abbiamo, inoltre, valutato questa variante empiricamente su alcuni MDP continui.