On the accuracy of state-action Laplacian representations for model free reinforcement learning

Learning state representations in Markov Decision Processes (MDPs) has proven to be crucial for addressing the curse of dimensionality in large-scale reinforcement learning problems. A widely recognized approach exploits structural priors in the MDP by constructing state representation as a linear combination of a subset of the state-graph Laplacian eigenvectors. However, this typically requires prior knowledge of the graph Laplacian or model-based Reinforcement Learning (RL) approaches to build a sample-based estimate of the graph. Recent works propose a way to learn the top Laplacian eigenvectors without prior knowledge of the graph, in a model-free fashion. In this work, we prove an upper bound on the approximation error of value functions estimators that are linear in such learned spectral features. Additionally, we switch from V-function to Q-function estimation, learning state-action representations. The latter play a key role in contemporary RL theory, but are less studied in the graph-based representation literature. We empirically validate our findings by solving policy evaluation tasks in benchmark environments, comparing our approach with other widespread function approximation techniques.

L’apprendimento di rappresentazioni degli stati nei Processi Decisionali di Markov (MDP) si è rivelato cruciale per affrontare il problema dell’alta dimensionalità nei problemi di apprendimento per rinforzo su larga scala. Un approccio ampiamente riconosciuto sfrutta conoscenze strutturali a priori dell’MDP costruendo come rappresentazione degli stati una combinazione lineare di un sottoinsieme degli autovettori del Laplaciano del grafo costruito sugli stati del MDP. Tuttavia, ciò richiede tipicamente una conoscenza preliminare del Laplaciano del grafo o l’uso di metodi di apprendimento per rinforzo model-based per costruire il grafo a partire dai campioni. Recenti lavori propon- gono un metodo per apprendere gli autovettori del Laplaciano senza conoscenza a priori del grafo, in modo completamente model-free. In questo lavoro, dimostriamo un limite superiore sull’errore di approssimazione degli stimatori della funzione Q che sono lineari rispetto alla rappresentazione spettrale precedentemente citata. Inoltre, passiamo dalla stima della funzione V alla stima della funzione Q, apprendendo rappresentazioni per ogni coppia stato-azione. Queste ultime svolgono un ruolo chiave nella teoria moderna dell’apprendimento per rinforzo, ma sono meno studiate nella letteratura sulle rappresentazioni basate su grafi. Validiamo empiricamente i nostri risultati risolvendo problemi di policy evaluation in ambienti di benchmark, confrontando il nostro approccio con altre diffuse tecniche di approssimazione di funzioni.