An Analysis of Laplacian Methods for Value Function Approximation in MDPs

Marek PetrikIJCAI 2007 · OpenReview

Abstract

Value function approximation is a critical component of reinforcement learning in large state spaces. While spectral methods like Proto-Value Functions (PVFs) have gained popularity for automated basis construction, they often lack a direct connection to the underlying reward structure and transition dynamics. This paper reframes value function approximation as a linear system solution, proposing Augmented Krylov (KA) methods as a superior alternative. We demonstrate that KA methods are significantly more efficient and robust to non-smooth reward functions compared to traditional Laplacian-based approaches.

Introduction

In Markov Decision Processes (MDPs), the value function $V^\pi$ represents the expected long-term reward under a policy $\pi$. For large-scale problems, storing $V^\pi$ explicitly is infeasible, necessitating Value Function Approximation (VFA). VFA represents the value function as a linear combination of basis vectors. Historically, these bases were manually engineered. The introduction of Proto-Value Functions (PVFs) marked a shift toward automated basis generation using the eigenvectors of a graph Laplacian. However, PVFs primarily focus on the "smoothness" of the state space graph, often ignoring the transition probabilities $P$ and the specific reward vector $r$.

Methods: From Graph Theory to Linear Algebra

Marek Petrik reframes the value function calculation as solving a linear system: $$v = (I - \gamma P)^{-1}r$$ where $\gamma$ is the discount factor. This perspective allows the application of robust tools from numerical linear algebra. We explore three primary methods:

  1. Weighted Spectral Method (WL): Utilizes the eigenvectors of the transition matrix $P$, selected based on their alignment with the reward vector $r$.
  2. Krylov Subspace Methods: Constructs a basis from the sequence $\{r, Pr, P^2r, \dots, P^m r\}$, capturing how rewards propagate through the environment over time.
  3. Augmented Krylov Method (KA): Our primary contribution, which augments a small set of top eigenvectors (capturing global structure) with Krylov vectors (capturing local reward dynamics).

The Augmented Krylov method is implemented using a modified Gram-Schmidt process to ensure numerical stability and orthonormality.

Algorithm for Augmented Krylov (KA) basis construction using a modified Gram-Schmidt process.

Experimental Evaluation

We evaluated these methods in a Two-Room Grid World environment consisting of 200 states. To test the robustness of the bases, we employed three distinct reward functions:

  • Reward 1: A smooth function easily captured by spectral methods.
  • Reward 2 & 3: Engineered to be "non-smooth" or nearly perpendicular to the top Laplacian eigenvectors, representing challenging scenarios for traditional PVFs.

Results and Discussion

Our results indicate that Krylov-based methods consistently outperform Laplacian approaches in both accuracy and computational efficiency.

Accuracy and Robustness

As shown in the performance plots, the Augmented Krylov (KA) and pure Krylov methods achieve near-zero Mean Squared Error (MSE) much faster than the Laplacian method. In the "Reward 3" case, the Laplacian method fails to reduce error significantly, whereas Krylov methods maintain high precision. This demonstrates that Krylov methods are not reliant on the "smoothness" assumption, making them more versatile for complex reward landscapes.

Comparison of Mean Squared Error (MSE) for Laplacian, WL, Krylov, and KA methods across three reward types.

Computational Efficiency

Krylov methods offer a significant speed advantage. On a standard benchmark, calculating 50 eigenvectors required 2.99 seconds, while generating 50 Krylov vectors took only 0.24 seconds. This order-of-magnitude improvement stems from the reliance on matrix-vector multiplications rather than full eigendecomposition, which is particularly beneficial for the sparse transition matrices typical of MDPs.

Conclusion

By bridging the gap between reinforcement learning and numerical analysis, we have shown that Augmented Krylov methods provide a more principled and efficient framework for value function approximation. While future work is needed to extend these methods to sampled data and online policy iteration, the foundational results suggest that reward-aware basis construction is a powerful tool for scaling RL algorithms.

Summary updated

Abstract

Recently, a method based on Laplacian eigenfunctions was proposed to automatically construct a basis for value function approximation in MDPs. We show that its success may be explained by drawing a connection between the spectrum of the Laplacian and the value function of the MDP. This explanation helps us to identify more precisely the conditions that this method requires to achieve good performance. Based on this, we propose a modification of the Laplacian method for which we derive an analytical bound on the approximation error. Further, we show that the method is related the augmented Krylov methods, commonly used to solve sparse linear systems. Finally, we empirically demonstrate that in basis construction the augmented Krylov methods may significantly outperform the Laplacian methods in terms of both speed and quality.
BibTeX
@inproceedings{petrik2007analysis,
  author = {Marek Petrik},
  title = {{An Analysis of Laplacian Methods for Value Function Approximation in MDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=B1N2iHz_ZH},
}
Figure