Impact of Connectivity on Laplacian Representations in Reinforcement Learning

Learning compact state representations in Markov Decision Processes (MDPs) has proven crucial for addressing the curse of dimensionality in large-scale reinforcement learning (RL) problems. Existing principled approaches leverage structural priors on the MDP by constructing state representations as linear combinations of the state-graph Laplacian eigenvectors. When the transition graph is unknown or the state space is prohibitively large, the graph spectral features can be estimated directly via sample trajectories. In this work, we prove an upper bound on the approximation error of linear value function approximation under the learned spectral features. We show how this error scales with the algebraic connectivity of the state-graph, grounding the approximation quality in the topological structure of the MDP. We further bound the error introduced by the eigenvector estimation itself, leading to an end-to-end error decomposition across the representation learning pipeline. Additionally, we show how the common expression for the symmetrized MDP Laplacian is easy to misinterpret, and propose a more straightforward reformulation. Our results hold for general (non-uniform) policies without any assumptions on the symmetry of the induced transition kernel. We validate our theoretical findings with numerical simulations on gridworld environments.

Reinforcement learning is a way to train an artificial agent to make decisions through experience, but learning in environments with many possible states can be computationally difficult. One common solution is to use a compact representation of the states. A well-known approach views the environment as a graph: a network in which states are connected according to the probability of moving from one state to another. A mathematical object derived from this graph, called the graph Laplacian, provides eigenvectors that can be used as compact representations. However, it has been unclear when this representation works well, especially when it must be learned from experience rather than given in advance. We show that when this network is poorly connected, with bottlenecks or narrow passages, the representation can work poorly. We also quantify the extra error caused by learning this representation from data. These results help researchers to decide when Laplacian representation is a good fit, and when the environment’s structure may make it less reliable.