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.
Figures & tables
Figure 1: Shows the error between the true value function v and approximate one. Two baselines are considered: the analytical case where the representation is obtained truncating the exact eigenvectors and its approximation obtained by optimizing GDO.
Figure 2: On the y-axis shows the log scale value assumed by λ2 , when the number of obstacles (walls) increases, or equivalently decreases the connectivity of the graph.
Figure 3: Shows the error of the analytical representation varying the number of eigenvectors k . On the y-axis we display the log scale value of the error, while on the x-axis the cut index k .
Figure 4: Shows the relationship between the second eigenvalue λ2 and the error using the approximated representation via GDO. On the y-axis we display the value of the error, while on the x-axis the values assumed by λ2 , both metrics vary with respect to the number of walls considered.
Figure 5: Shows the relationship between the second eigenvalue λ2 and the error using the analytical eigenvector representation. On the y-axis we display the value of the error, while on the x-axis the values assumed by λ2 , both metrics vary with respect to the number of walls considered.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: 30x30 gridworld with 5 walls with its corresponding graph visualization
Figure 7: 30x30 gridworld with 116 walls with its corresponding graph visualization
Figure 8: 30x30 gridworld with 283 walls with its corresponding graph visualization
Figure 9: 30x30 gridworld with 449 walls with its corresponding graph visualization
η
λ2
εana
εGDO
0
0.0109
0.172
1.81±0.0244
0.1
0.110
0.124
0.323±0.0155
0.2
0.209
0.0928
0.187±0.00523
0.3
0.308
0.0706
0.128±0.00277
0.4
0.407
0.0538
0.0924±0.000831
0.5
0.506
0.0405
0.0662±0.000249
Appendix
Table 1: Values of λ2 , analytical error εana , and GDO error εGDO for different values of η .
Figure 10: Effect of stochastic transitions on connectivity and approximation error. Increasing the stochasticity parameter η improves the algebraic connectivity λ2 and reduces both the analytical error εana and the GDO-based error εGDO .
Figure 11: Policy-evaluation errors across different reward tasks when the representation is computed via GDO. Representation is truncated at k=20 , on a 10×10 grid, results averaged over 5 seeds. Each task corresponds to a different goal location. Across tasks, better connected transition graphs lead to smaller GDO-based approximation errors. In most of the tasks GDO exhibit higher error compared to analytical, but it preserves the same increasing trend as the connectivity of the graph shrinks due to walls.
Figure 12: Policy-evaluation errors across different reward tasks, using the analytical representation. Representation is truncated at k=20 , on a 10×10 grid, results averaged over 5 seeds. Each task corresponds to a different goal location. Across tasks, better connected transition graphs lead to smaller analytical approximation errors.
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying linear Bellman completeness -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with deterministic transitions, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an ε-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and 1/ε.
Learning a compact model of the world from interaction data is central to sample-efficient deep reinforcement learning. Spectral representation methods have become the leading paradigm for representation learning in continuous control by taking a matrix view of the transition kernel, with state-action pairs on one side and next states on the other, and learning a low-rank factorization through self-supervised contrastive objectives. We take this view one step further. The transition kernel is naturally a three-mode tensor over states, actions, and next states, and a CP decomposition gives one feature map per mode. We propose FaStR, which fits this decomposition with a noise contrastive objective, producing separate state, action, and next-state encoders that together form a single spectral representation. The factored form yields a smaller hypothesis class, and the sample size needed for representation learning shrinks by a factor that scales with the smaller of the state and action dimensions. Empirically, FaStR delivers its largest gains on high-dimensional locomotion tasks whose dynamics align with the factored structure, and the learned state encoder transfers intact across actuator shift while only the action encoder is retrained.
Junyi Wu, Dan Li
Department of Industrial and Systems Engineering University of Washington Seattle, WA, USA
In Networked Markov Decision Processes, transition dynamics are often unknown and the state--action space grows rapidly with the number of agents. In this setting, Taylor representations naturally approximate Q-functions, but a naive order-n expansion over N agents requires Θ(Nn) coefficients. We justify these expansions under smooth expected future local rewards with controlled derivatives. Under this condition, finite-speed information propagation and discounting imply that local-critic Taylor coefficients decay exponentially with the graph distance to the farthest agent involved. Discarding distant-agent coefficients and marginalizing then yield scalable local Taylor representations with a bound controlled by graph locality. Building on these representations, we propose a scalable model-free actor--critic algorithm, establishing finite-sample critic and near-stationarity guarantees for a linear LSTD critic. We then introduce a more expressive neural TD parameterization. Unlike prior constructive spectral methods, our approach covers settings without access to a known local dynamics map, such as hidden switched linear--quadratic regulation. Across three control benchmarks, our method matches or outperforms spectral baselines while scaling efficiently to large graphs.