In machine learning, automatic basis function construction (or basis discovery) is the mathematical method of looking for a set of task-independent basis functions that map the state space to a lower-dimensional embedding, while still representing the value function accurately. Automatic basis construction is independent of prior knowledge of the domain, which allows it to perform well where expert-constructed basis functions are difficult or impossible to create.

Motivation

In reinforcement learning (RL), most real-world Markov Decision Process (MDP) problems have large or continuous state spaces, which typically require some sort of approximation to be represented efficiently.

Automatic basis function construction

Linear function approximators (LFAs) are widely adopted for their low theoretical complexity. Two sub-problems needs to be solved for better approximation: weight optimization and basis construction. To solve the second problem, one way is to design special basis functions. Those basis functions work well in specific tasks but are significantly restricted to domains. Thus constructing basis construction functions automatically is preferred for broader applications.

Automatic basis function construction

Problem definition

A Markov decision process with finite state space and fixed policy is defined with a 5-tuple , which includes the finite state space , the finite action space , the reward function , discount factor , and the transition model .

Automatic basis function construction

Bellman equation is defined as:

When the number of elements in is small, is usually maintained as tabular form. While grows too large for this kind of representation. is commonly being approximated via a linear combination of basis function , so that we have:

Here is a matrix in which every row contains a feature vector for corresponding row, is a weight vector with n parameters and usually .

Basis construction looks for ways to automatically construct better basis function which can represent the value function well.

A good construction method should have the following characteristics:

Small error bounds between the estimate and real value function

Form orthogonal basis in the value function space

Converge to stationary value function fast

Popular methods

Proto-value basis

In this approach, Mahadevan analyzes the connectivity graph between states to determine a set of basis functions.

The normalized graph Laplacian is defined as:

Here W is an adjacency matrix which represents the states of fixed policy MDP which forms an undirected graph (N,E). D is a diagonal matrix related to nodes' degrees.

In discrete state space, the adjacency matrix could be constructed by simply checking whether two states are connected, and D could be calculated by summing up every row of W. In continuous state space, we could take random walk Laplacian of W.

This spectral framework can be used for value function approximation (VFA). Given the fixed policy, the edge weights are determined by corresponding states' transition probability. To get smooth value approximation, diffusion wavelets are used.

Krylov basis

Krylov basis construction uses the actual transition matrix instead of random walk Laplacian. The assumption of this method is that transition model P and reward r are available.

The vectors in Neumann series are denoted as

for all .

It shows that Krylov space spanned by is enough to represent any value function, and m is the degree of minimal polynomial of .

Suppose the minimal polynomial is , and we have , the value function can be written as:

Algorithm Augmented Krylov Method

are top real eigenvectors of P

for do

if then

; end if for do

end for

if then

break; end if end for k: number of eigenvectors in basis l: total number of vectors

Bellman error basis

Bellman error (or BEBFs) is defined as: .

Loosely speaking, Bellman error points towards the optimal value function. The sequence of BEBF form a basis space which is orthogonal to the real value function space; thus with sufficient number of BEBFs, any value function can be represented exactly. Algorithm BEBF stage stage i=1, ; stage compute the weight vector according to current basis function ; compute new bellman error by ; add bellman error to form new basis function: ; N represents the number of iterations till convergence. ":" means juxtaposing matrices or vectors.

Bellman average reward bases

Bellman Average Reward Bases (or BARBs) is similar to Krylov Bases, but the reward function is being dilated by the average adjusted transition matrix . Here can be calculated by many methods in.