Apprendimento orientato alle decisioni negli MDP: un approccio basato sulle misure di occupazione

Abstract degli autori

In questo lavoro esaminiamo l’apprendimento orientato alle decisioni (DFL) per un processo decisionale di Markov (MDP). I metodi esistenti calcolano le derivate attraverso le condizioni KKT dell’equazione di Bellman e richiedono di risolvere un sistema lineare che coinvolge tutte le coppie stato-azione, limitando così la loro scalabilità. Per superare questo limite, riformuliamo l’MDP come un problema di programmazione lineare (LP) basato sulle misure di occupazione, la cui regione ammissibile è determinata dalle dinamiche previste. Ricaviamo poi un gradiente in forma chiusa individuando i vincoli attivi nel poliedro ammissibile mediante l’algoritmo di pivot. Questo livello LP basato sulle misure di occupazione presenta due difficoltà: (1) il gradiente della soluzione dell’LP è discontinuo quando cambiano i vincoli attivi e (2) il costo della retropropagazione dell’LP continua a crescere con la dimensione dello spazio degli stati, risultando elevato per spazi degli stati grandi o continui. Affrontiamo queste difficoltà con un surrogato lagrangiano aumentato, attenuando i salti al confine mediante lo sketching casuale delle righe dei vincoli, e con un livello apprendibile di aggregazione soft degli stati e la sua generalizzazione tramite approssimazione di funzioni, che rendono l’LP scalabile per MDP con spazi degli stati finiti di grandi dimensioni o continui. In diversi compiti, i nostri metodi ottengono un regret inferiore rispetto al DFL basato sulle condizioni KKT e ai metodi di riferimento a due fasi, con un costo computazionale significativamente più basso. Il codice sorgente di tutti gli esperimenti è disponibile all’indirizzo https://github.com/A-Eshragh/State_Aggregation_Project.