Proto-value function
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. For the sake of simplicity, assume that the underlying state space can be represented as an undirected unweighted graph G=(V,E) The combinatorial Laplacian L is defined as the operator L = D - A , where D is a diagonal matrix called the degree matrix and A is the adjacency matrix. The spectral analysis of the Laplace operator on a graph consists of finding the eigenvalues and eigenfunctions which solve the equation L\varphi_\lambda = \lambda\varphi_\lambda, where L is the combinatorial Laplacian, \varphi_\lambda is an eigenfunction associated with the eigenvalue \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. The combinatorial Laplacian is not the only operator on graphs to select from. Other possible graph operators include: Normalized Laplacian L_\text{normalized} = I - D^{-1/2}AD^{-1/2} Random Walk P = D^{-1}A G_{i,j}=\begin{cases} 1 & \text{if } S_i\leftrightarrow S_j \\ 0 & \text{otherwise} \end{cases} This can only be done when the state space is finite and of reasonable size. Let \Phi_G=\left\{ V_1^G,\dots,V_k^G\right\} be the basis set of PVFs, where each V_i^G is the eigenfunction defined over all states in the graph G . Let \widehat{V}^\pi be the target value function that is only known for a subset of states S_M^G =\left\{ s_1,\dots,s_m\right\} . Define the gram matrix K_G =\left(\Phi_m^G \right)^T \Phi_m^G. Here S_m^G is the component wise projection of the PVFs onto the states in S_G^m . Hence, each entry of the gram matrix is 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 \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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1348246306 under CC BY-SA 4.0; modifications have been made.