Proto-value function

In applied mathematics, proto-value functions (PVFs) are automatically learned basis functions that are useful in approximating task-specific value functions, providing a compact representation of the powers of transition matrices. They provide a novel framework for solving the credit assignment problem. The framework introduces a novel approach to solving Markov decision processes (MDP) and reinforcement learning problems, using multiscale spectral and manifold learning methods. Proto-value functions are generated by spectral analysis of a graph, using the graph Laplacian.

Proto-value functions were first introduced in the context of reinforcement learning by Sridhar Mahadevan in his paper, Proto-Value Functions: Developmental Reinforcement Learning at ICML 2005. ^[1]

Motivation

Value function approximation is a critical component to solving Markov decision processes (MDPs) defined over a continuous state space. A good function approximator allows a reinforcement learning (RL) agent to accurately represent the value of any state it has experienced, without explicitly storing its value. Linear function approximation using basis functions is a common way of constructing a value function approximation, like radial basis functions, polynomial state encodings, and CMACs. However, parameters associated with these basis functions often require significant domain-specific hand-engineering. ^[2] Proto-value functions attempts to solve this required hand-engineering by accounting for the underlying manifold structure of the problem domain. ^[1]

Overview

Proto-value functions are task-independent global basis functions that collectively span the entire space of possible value functions for a given state space. ^[1] They incorporate geometric constraints intrinsic to the environment. For example, states close in Euclidean distance (such as states on opposite sides of a wall) may be far apart in manifold space. Previous approaches to this nonlinearity problem lacked a broad theoretical framework, and consequently have only been explored in the context of discrete MDPs.

Proto-value functions arise from reformulating the problem of value function approximation as real-valued function approximation on a graph or manifold. This results in broader applicability of the learned bases and enables a new class of learning algorithms, which learn representations and policies at the same time. ^[3]

Basis functions from graph Laplacian

This approach constructs the basis functions by spectral analysis of the graph Laplacian, a self-adjoint (or symmetric) operator on the space of functions on the graph, closely related to the random walk operator.

For the sake of simplicity, assume that the underlying state space can be represented as an undirected unweighted graph ${\displaystyle G=(V,E)}$ The combinatorial Laplacian ${\displaystyle L}$ is defined as the operator ${\displaystyle L=D-A}$, where ${\displaystyle D}$ is a diagonal matrix called the degree matrix and ${\displaystyle A}$ is the adjacency matrix. ^[1]

The spectral analysis of the Laplace operator on a graph consists of finding the eigenvalues and eigenfunctions which solve the equation

${\displaystyle L\varphi _{\lambda }=\lambda \varphi _{\lambda },}$

where ${\displaystyle L}$ is the combinatorial Laplacian, ${\displaystyle \varphi _{\lambda }}$ is an eigenfunction associated with the eigenvalue ${\displaystyle \lambda }$. Here the term "eigenfunction" is used to denote what is traditionally referred to as eigenvector in linear algebra, because the Laplacian eigenvectors can naturally be viewed as functions that map each vertex to a real number. ^[3]

The combinatorial Laplacian is not the only operator on graphs to select from. Other possible graph operators include:

• Normalized Laplacian ${\displaystyle L_{\text{normalized}}=I-D^{-1/2}AD^{-1/2}}$ ^[4]
• Random Walk ${\displaystyle P=D^{-1}A}$ ^[4]

Graph construction on discrete state space

For a finite state space the graph ${\displaystyle G}$ mentioned above can be simply constructed by examining the connections between states. Let ${\displaystyle S_{i}}$ and ${\displaystyle S_{j}}$ be any two states. Then

${\displaystyle G_{i,j}={\begin{cases}1&{\text{if }}S_{i}\leftrightarrow S_{j}\\0&{\text{otherwise}}\end{cases}}}$

It is important to note that this can only be done when the state space is finite and of reasonable size.

Graph construction on continuous or large state space

For a continuous state space or simply a very large discrete state space, it is necessary to sample from the manifold in state space. Then constructing the Graph ${\displaystyle G}$ based on the samples. There are a few issues to consider here: ^[4]

• How to sample the manifold
  • Random walk or guided exploration
• How to determine if two sample should be connected

Application

Once the PVFs are generated, they can be plugged into a traditional function approximation framework. One such method is least-squares approximation.

Least-squares approximation using proto-value functions

Let ${\displaystyle \Phi _{G}=\left\{V_{1}^{G},\dots ,V_{k}^{G}\right\}}$ be the basis set of PVFs, where each ${\displaystyle V_{i}^{G}}$ is the eigenfunction defined over all states in the graph ${\displaystyle G}$. Let ${\displaystyle {\widehat {V}}^{\pi }}$ be the target value function that is only known for a subset of states ${\displaystyle S_{M}^{G}=\left\{s_{1},\dots ,s_{m}\right\}}$.

Define the gram matrix

${\displaystyle K_{G}=\left(\Phi _{m}^{G}\right)^{T}\Phi _{m}^{G}.}$

Here ${\displaystyle S_{m}^{G}}$ is the component wise projection of the PVFs onto the states in ${\displaystyle S_{G}^{m}}$. Hence, each entry of the gram matrix is

${\displaystyle K_{G}(i,j)=\sum _{k}V_{i}^{G}(k)V_{j}^{G}(k).}$

The coefficients that minimize the least squares error are then described by the equation

${\displaystyle \alpha =K_{G}^{-1}\left(\Phi _{M}^{G}\right)^{T}{\widehat {V}}^{\pi }.}$

A nonlinear least-squares approach is possible by using the k PVFs with the largest absolute coefficients to compute the approximation. ^[1]

See also

• Reinforcement learning
• Markov decision process
• Basis function
• Eigenfunction
• Laplacian matrix

References

1. Mahadevan, S. Proto-Value Functions: Developmental Reinforcement Learning. Proceedings of the International Conference on Machine Learning ICML 2005
2. Johns, J. and Mahadevan, S., Constructing Basis Functions from Directed Graphs for Value Function Approximation, International Conference on Machine Learning (ICML), 2007
3. Mahadevan, S. and Maggiono, M., Proto-Value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes, University of Massachusetts, Department of Computer Science Technical Report TR-2006-35, 2006
4. Mahadevan, S. and Maggiono, M., ICML 2006 tutorial.