# Impact of Connectivity on Laplacian Representations in Reinforcement Learning

arXiv: https://arxiv.org/abs/2603.08558 · HTML: https://mlsanity.com/paper/2603.08558/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 9 Mar 2026.

## Placed in

- Deep reinforcement learning methods / [Deep RL algorithms and representations](https://mlsanity.com/deeprl/deep-rl-algorithms-and-representations/)

## Builds on (most cited first, 14 of 14)

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Contrastive Learning as Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2206.07568/) (2022)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [The Laplacian in RL: Learning Representations with Efficient Approximations](https://mlsanity.com/paper/1810.04586/) (2018)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Proto-Value Networks: Scaling Representation Learning with Auxiliary Tasks](https://mlsanity.com/paper/2304.12567/) (2023)
- [Spectral Decomposition Representation for Reinforcement Learning](https://mlsanity.com/paper/2208.09515/) (2022)
- [On the Generalization of Representations in Reinforcement Learning](https://mlsanity.com/paper/2203.00543/) (2022)
- [Towards Better Laplacian Representation in Reinforcement Learning with Generalized Graph Drawing](https://mlsanity.com/paper/2107.05545/) (2021)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures](https://mlsanity.com/paper/2309.14298/) (2023)
- [Reachability-Aware Laplacian Representation in Reinforcement Learning](https://mlsanity.com/paper/2210.13153/) (2022)

## Built on by (most cited first, 1 of 1)

- [Topology-Aware State Abstraction with Tangle Cores for Markov Decision Processes](https://mlsanity.com/paper/2606.00427/) (2026)

## Abstract (arXiv)

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, our expression of the Laplacian operator for the RL setting, although equivalent to existing ones, prevents some common misunderstandings, of which we show some examples from the literature. 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.