Automatic basis function construction

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

The normalized graph Laplacian is defined as:

${\displaystyle L=I-D^{-{\frac {1}{2}}}WD^{-{\frac {1}{2}}}}$

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 ${\displaystyle W}$ 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.[3]

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 ${\displaystyle y_{i}=P^{i}r}$ for all ${\displaystyle i\in [0,infty)}$.

It shows that Krylov space spanned by ${\displaystyle y_{0},y_{1},\ldots ,y_{m-1}}$ is enough to represent any value function,[4] and m is the degree of minimal polynomial of ${\displaystyle (I-\gamma P)}$.

Suppose the minimal polynomial is ${\displaystyle p(A)={\frac {1}{\alpha _{0}}}\sum _{i=0}^{m-1}\alpha _{i+1}A^{i}}$, and we have ${\displaystyle BA=I}$, the value function can be written as:

${\displaystyle v=Br={\frac {1}{\alpha _{0}}}\sum _{i=0}^{m-1}\alpha _{i+1}(I-\gamma P)^{i}r=\sum _{i=0}^{m-1}\alpha _{i+1}\beta _{i}y_{i}.}$[5]

Algorithm Augmented Krylov Method[5]

${\displaystyle z_{1},z_{2},\ldots ,z_{k}}$ are top real eigenvectors of P

${\displaystyle z_{k+1}:=r}$

for ${\displaystyle i:=1:(l+k)}$ do

if ${\displaystyle i>k+1}$ then

${\displaystyle z_{i}:=Pz_{i-1}}$;

end if

for ${\displaystyle j:=1:(i-1)}$ do

${\displaystyle z_{i}:=z_{i}-<z_{j},z_{i}>z_{j};}$

end for

if ${\displaystyle \parallel z_{i}\parallel \approx 0}$ then

break;

end if

end for

• k: number of eigenvectors in basis
• l: total number of vectors

Bellman error (or BEBFs) is defined as: ${\displaystyle \varepsilon =r+\gamma P{\hat {v}}-{\hat {v}}=r+\gamma P\Phi \theta -\Phi \theta }$.

Loosely speaking, Bellman error points towards the optimal value function.[6] 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, ${\displaystyle \phi _{1}=r}$;

stage ${\displaystyle i\in [2,N]}$

compute the weight vector ${\displaystyle \theta _{i}}$ according to current basis function ${\displaystyle \Phi _{i}}$;

compute new bellman error by ${\displaystyle \varepsilon =r+\gamma P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}}$;

add bellman error to form new basis function: ${\displaystyle \Phi _{i+1}=[\Phi _{i}:\varepsilon ]}$;

• N represents the number of iterations till convergence.
• ":" means juxtaposing matrices or vectors.

Bellman Average Reward Bases (or BARBs)[7] is similar to Krylov Bases, but the reward function is being dilated by the average adjusted transition matrix ${\displaystyle P-P^{*}}$. Here ${\displaystyle P^{*}}$ can be calculated by many methods in.[8]

BARBs converges faster than BEBFs and Krylov when ${\displaystyle \gamma }$ is close to 1.

Algorithm BARBs

stage stage i=1, ${\displaystyle P^{*}r}$;

stage ${\displaystyle i\in [2,N]}$

compute the weight vector ${\displaystyle \theta _{i}}$ according to current basis function ${\displaystyle \Phi _{i}}$;

compute new basis: ${\displaystyle$ :\phi _{i+1}=r-P^{*}r+P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}} , and add it to form new bases matrix${\displaystyle \Phi _{i+1}=[\Phi _{i}:\phi _{i+1}]}$;

• N represents the number of iterations till convergence.
• ":" means juxtaposing matrices or vectors.