Impact of Connectivity on Laplacian Representations in Reinforcement Learning

• URL: http://arxiv.org/abs/2603.08558v1
• Date: Mon, 09 Mar 2026 16:20:31 GMT
• Title: Impact of Connectivity on Laplacian Representations in Reinforcement Learning
• Abstract summary: We show an upper bound on the approximation error of linear value function approximation under the learned spectral features.<n>We further bound the error introduced by the eigenvector estimation itself, leading to an end-to-end error decomposition.<n>Our results hold for general (non-uniform) policies without any assumptions on the symmetry of the induced transition kernel.
• Score: 9.306521175972588
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Difference-of-Convex Regularization for Graph Learning by Differentiable Programming [1.9651461643699661]
  We propose a Difference-of-Convex Regularizer (DCR) graph learning framework that approximates the spectral action of the Laplacian pseudoinverse without direct inversion.<n>By reformulating Laplacian-Regularized Nonnegative Least Squares (LR-NNLS) through a dual representation, DCR decouples pseudoinverse learning from instance-specific inference.<n>We establish theoretical guarantees on stability and the existence of a unique fixed point for DCR algorithm.
  arXiv  Detail & Related papers  (2026-08-13T03:10:05Z)
• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• Nonparametric Identification and Inference for Counterfactual Distributions with Confounding [6.997978440999076]
  We propose nonparametric identification and semiparametric estimation of joint potential outcome in the presence of confounding.<n>By bridging classical semiparametric theory with modern representation learning, this work provides a robust statistical foundation for distributional and counterfactual inference in complex causal systems.
  arXiv  Detail & Related papers  (2026-02-17T05:00:13Z)
• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  We introduce SIGMA (Spectral Inequalities for Gram Matrix Analysis), a unified framework for model collapse.<n>By utilizing benchmarks that deriving and deterministic bounds on the matrix's spectrum, SIGMA provides a mathematically grounded metric to track the contraction of the representation space.<n>We demonstrate that SIGMA effectively captures the transition towards states, offering both theoretical insights into the mechanics of collapse.
  arXiv  Detail & Related papers  (2026-01-06T19:47:11Z)
• The Vekua Layer: Exact Physical Priors for Implicit Neural Representations via Generalized Analytic Functions [0.0]
  Implicit Neural Representations (INRs) have emerged as a powerful paradigm for parameterizing physical fields.<n>We introduce a differentiable spectral method grounded in the Generalized Analytic theory.<n>We show that our method can effectively act as a physics-informed spectral filter.
  arXiv  Detail & Related papers  (2025-12-11T21:57:21Z)
• Asymptotics of Linear Regression with Linearly Dependent Data [28.005935031887038]
  We study the computations of linear regression in settings with non-Gaussian covariates.<n>We show how dependencies influence estimation error and the choice of regularization parameters.
  arXiv  Detail & Related papers  (2024-12-04T20:31:47Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  Recent work has built the connection between self-supervised learning and the approximation of the top eigenspace of a graph Laplacian operator. This work delves into a statistical analysis of augmentation-based pretraining.
  arXiv  Detail & Related papers  (2023-06-01T15:18:55Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.