Automatic basis function construction

<h2 id="motivation">Motivation</h2>
In <a href="/facts/Reinforcement_learning/NrgPPS0Q">reinforcement learning</a> (RL), many real-world problems modeled as <a href="/facts/Markov_Decision_Processes/cVlWIDrw">Markov Decision Processes</a> (MDPs) involve large or continuous <a href="/facts/State_space/H1vjb3LL">state spaces</a>—sets of all possible situations an agent might encounter—which are too complex to handle directly and often need approximation for efficient computation.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> 
Linear function approximators<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> (LFAs), valued for their simplicity and low computational demands, are a common solution. Using LFAs effectively requires addressing two challenges: optimizing weights (adjusting importance of features) and building basis functions (creating simplified representations). While specially designed basis functions can excel in specific tasks, they are limited to those particular areas (domains). Automatic basis function construction offers a more flexible approach, enabling broader use across diverse problems without relying on task-specific expertise.

<h2 id="problem-definition">Problem definition</h2>
A Markov decision process with finite state space and fixed policy is defined with a 5-tuple 
 
 
 
 
 s
 ,
 a
 ,
 p
 ,
 γ
 ,
 r
 
 
 
 {\displaystyle {s,a,p,\gamma ,r}}
 
, which includes the finite state space 
 
 
 
 S
 =
 
 1
 ,
 2
 ,
 …
 ,
 s
 
 
 
 {\displaystyle S={1,2,\ldots ,s}}
 
, the finite action space 
 
 
 
 A
 
 
 {\displaystyle A}
 
, the reward function 
 
 
 
 r
 
 
 {\displaystyle r}
 
, discount factor 
 
 
 
 γ
 ∈
 [
 0
 ,
 1
 )
 
 
 {\displaystyle \gamma \in [0,1)}
 
, and the transition model 
 
 
 
 P
 
 
 {\displaystyle P}
 
.
Bellman equation is defined as:

v
        =
        r
        +
        γ
        P
        v
        .
        
      
    
    {\displaystyle v=r+\gamma Pv.\,}

When the number of elements in 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is small, 
 
 
 
 v
 
 
 {\displaystyle v}
 
 is usually maintained as tabular form. While 
 
 
 
 S
 
 
 {\displaystyle S}
 
 grows too large for this kind of representation. 
 
 
 
 v
 
 
 {\displaystyle v}
 
 is commonly being approximated via a linear combination of basis function 
 
 
 
 Φ
 =
 
 
 ϕ
 
 1
 
 
 ,
 
 ϕ
 
 2
 
 
 ,
 …
 ,
 
 ϕ
 
 n
 
 
 
 
 
 {\displaystyle \Phi ={\phi _{1},\phi _{2},\ldots ,\phi _{n}}}
 
,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> so that we have:

v
        ≈
        
          
            
              v
              ^
            
          
        
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          θ
          
            n
          
        
        
          ϕ
          
            n
          
        
      
    
    {\displaystyle v\approx {\hat {v}}=\sum _{i=1}^{n}\theta _{n}\phi _{n}}

Here 
 
 
 
 Φ
 
 
 {\displaystyle \Phi }
 
 is a 
 
 
 
 
 |
 
 S
 
 |
 
 ×
 n
 
 
 {\displaystyle |S|\times n}
 
 matrix in which every row contains a <a href="/facts/Feature_(machine_learning)/nzAhYxfu">feature vector</a> for corresponding row, 
 
 
 
 θ
 
 
 {\displaystyle \theta }
 
 is a weight vector with n parameters and usually 
 
 
 
 n
 ≪
 
 |
 
 s
 
 |
 
 
 
 {\displaystyle n\ll |s|}
 
.
Basis construction looks for ways to automatically construct better basis function 
 
 
 
 Φ
 
 
 {\displaystyle \Phi }
 
 which can represent the value function well.
A good construction method should have the following characteristics:

<ul><li>Small error bounds between the estimate and real value function</li>
<li>Form <a href="/facts/Orthogonal_basis/H4DgNCgR">orthogonal basis</a> in the value function space</li>
<li>Converge to stationary value function fast</li></ul>
<h2 id="popular-methods">Popular methods</h2>
<h3>Proto-value basis</h3>
In this approach, Mahadevan analyzes the connectivity graph between states to determine a set of basis functions.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
The normalized graph Laplacian is defined as:

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

Here W is an <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> which represents the states of fixed policy MDP which forms an <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">undirected graph</a> (N,E). D is a <a href="/facts/Diagonal_matrix/tjIAHrE6">diagonal matrix</a> related to nodes' degrees.
In discrete state space, the adjacency matrix 
 
 
 
 W
 
 
 {\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 <a href="/facts/Random_walk/08v0jmfv">random walk</a> Laplacian of W.
This spectral framework can be used for value <a href="/facts/Function_approximation/Q9CDgIH4">function approximation</a> (VFA). Given the fixed policy, the edge weights are determined by corresponding states' transition probability. To get smooth value approximation, <a href="/facts/Diffusion_wavelets/1pNDupzJ">diffusion wavelets</a> are used.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h3>Krylov basis</h3>
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 <a href="/facts/Neumann_series/E6e3gyAK">Neumann series</a> are denoted as

y
 
 i
 
 
 =
 
 P
 
 i
 
 
 r
 
 
 {\displaystyle y_{i}=P^{i}r}
 
 for all 
 
 
 
 i
 ∈
 [
 0
 ,
 ∞
 )
 
 
 {\displaystyle i\in [0,\infty )}
 
.
It shows that Krylov space spanned by 
 
 
 
 
 y
 
 0
 
 
 ,
 
 y
 
 1
 
 
 ,
 …
 ,
 
 y
 
 m
 −
 1
 
 
 
 
 {\displaystyle y_{0},y_{1},\ldots ,y_{m-1}}
 
 is enough to represent any value function,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and m is the degree of minimal polynomial of 
 
 
 
 (
 I
 −
 γ
 P
 )
 
 
 {\displaystyle (I-\gamma P)}
 
.
Suppose the minimal polynomial is 
 
 
 
 p
 (
 A
 )
 =
 
 
 1
 
 α
 
 0
 
 
 
 
 
 ∑
 
 i
 =
 0
 
 
 m
 −
 1
 
 
 
 α
 
 i
 +
 1
 
 
 
 A
 
 i
 
 
 
 
 {\displaystyle p(A)={\frac {1}{\alpha _{0}}}\sum _{i=0}^{m-1}\alpha _{i+1}A^{i}}
 
, and we have 
 
 
 
 B
 A
 =
 I
 
 
 {\displaystyle BA=I}
 
, the value function can be written as:

v
 =
 B
 r
 =
 
 
 1
 
 α
 
 0
 
 
 
 
 
 ∑
 
 i
 =
 0
 
 
 m
 −
 1
 
 
 
 α
 
 i
 +
 1
 
 
 (
 I
 −
 γ
 P
 
 )
 
 i
 
 
 r
 =
 
 ∑
 
 i
 =
 0
 
 
 m
 −
 1
 
 
 
 α
 
 i
 +
 1
 
 
 
 β
 
 i
 
 
 
 y
 
 i
 
 
 .
 
 
 {\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}.}
 
<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Algorithm Augmented Krylov Method<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

z
 
 1
 
 
 ,
 
 z
 
 2
 
 
 ,
 …
 ,
 
 z
 
 k
 
 
 
 
 {\displaystyle z_{1},z_{2},\ldots ,z_{k}}
 
 are top real <a href="/facts/Eigenvalues_and_eigenvectors/8TjEoT8u">eigenvectors</a> of P

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

for 
 
 
 
 i
 :=
 1
 :
 (
 l
 +
 k
 )
 
 
 {\displaystyle i:=1:(l+k)}
 
 do
if 
 
 
 
 i
 >
 k
 +
 1
 
 
 {\displaystyle i>k+1}
 
 then

z
 
 i
 
 
 :=
 P
 
 z
 
 i
 −
 1
 
 
 
 
 {\displaystyle z_{i}:=Pz_{i-1}}
 
;
end if
for 
 
 
 
 j
 :=
 1
 :
 (
 i
 −
 1
 )
 
 
 {\displaystyle j:=1:(i-1)}
 
 do

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

end for
if 
 
 
 
 ∥
 
 z
 
 i
 
 
 ∥≈
 0
 
 
 {\displaystyle \parallel z_{i}\parallel \approx 0}
 
 then
break;
end if
end for
<ul><li>k: number of eigenvectors in basis</li>
<li>l: total number of vectors</li></ul>
<h3>Bellman error basis</h3>
Bellman error (or BEBFs) is defined as: 
 
 
 
 ε
 =
 r
 +
 γ
 P
 
 
 
 v
 ^
 
 
 
 −
 
 
 
 v
 ^
 
 
 
 =
 r
 +
 γ
 P
 Φ
 θ
 −
 Φ
 θ
 
 
 {\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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> The sequence of BEBF form a basis space which is orthogonal to the real value <a href="/facts/Function_space/lLUE2R1t">function space</a>; thus with sufficient number of BEBFs, any value function can be represented exactly.

Algorithm BEBF
stage stage i=1, 
 
 
 
 
 ϕ
 
 1
 
 
 =
 r
 
 
 {\displaystyle \phi _{1}=r}
 
;
stage 
 
 
 
 i
 ∈
 [
 2
 ,
 N
 ]
 
 
 {\displaystyle i\in [2,N]}

compute the weight vector 
 
 
 
 
 θ
 
 i
 
 
 
 
 {\displaystyle \theta _{i}}
 
 according to current basis function 
 
 
 
 
 Φ
 
 i
 
 
 
 
 {\displaystyle \Phi _{i}}
 
;
compute new bellman error by 
 
 
 
 ε
 =
 r
 +
 γ
 P
 
 Φ
 
 i
 
 
 
 θ
 
 i
 
 
 −
 
 Φ
 
 i
 
 
 
 θ
 
 i
 
 
 
 
 {\displaystyle \varepsilon =r+\gamma P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}}
 
;
add bellman error to form new basis function: 
 
 
 
 
 Φ
 
 i
 +
 1
 
 
 =
 [
 
 Φ
 
 i
 
 
 :
 ε
 ]
 
 
 {\displaystyle \Phi _{i+1}=[\Phi _{i}:\varepsilon ]}
 
;
<ul><li>N represents the number of iterations till convergence.</li>
<li>":" means juxtaposing matrices or vectors.</li></ul>
<h3>Bellman average reward bases</h3>
Bellman Average Reward Bases (or BARBs)<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> is similar to Krylov Bases, but the reward function is being dilated by the average adjusted transition matrix 
 
 
 
 P
 −
 
 P
 
 ∗
 
 
 
 
 {\displaystyle P-P^{*}}
 
. Here 
 
 
 
 
 P
 
 ∗
 
 
 
 
 {\displaystyle P^{*}}
 
 can be calculated by many methods in.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
BARBs converges faster than BEBFs and Krylov when 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 is close to 1.

Algorithm BARBs
stage stage i=1, 
 
 
 
 
 P
 
 ∗
 
 
 r
 
 
 {\displaystyle P^{*}r}
 
;
stage 
 
 
 
 i
 ∈
 [
 2
 ,
 N
 ]
 
 
 {\displaystyle i\in [2,N]}

compute the weight vector 
 
 
 
 
 θ
 
 i
 
 
 
 
 {\displaystyle \theta _{i}}
 
 according to current basis function 
 
 
 
 
 Φ
 
 i
 
 
 
 
 {\displaystyle \Phi _{i}}
 
;
compute new basis: 
 
 
 
 :
 
 ϕ
 
 i
 +
 1
 
 
 =
 r
 −
 
 P
 
 ∗
 
 
 r
 +
 P
 
 Φ
 
 i
 
 
 
 θ
 
 i
 
 
 −
 
 Φ
 
 i
 
 
 
 θ
 
 i
 
 
 
 
 {\displaystyle :\phi _{i+1}=r-P^{*}r+P\Phi _{i}\theta _{i}-\Phi _{i}\theta _{i}}
 
, and add it to form new bases matrix
 
 
 
 
 Φ
 
 i
 +
 1
 
 
 =
 [
 
 Φ
 
 i
 
 
 :
 
 ϕ
 
 i
 +
 1
 
 
 ]
 
 
 {\displaystyle \Phi _{i+1}=[\Phi _{i}:\phi _{i+1}]}
 
;
<ul><li>N represents the number of iterations till convergence.</li>
<li>":" means juxtaposing matrices or vectors.</li></ul>
<h2 id="discussion-and-analysis">Discussion and analysis</h2>
There are two principal types of basis construction methods.
The first type of methods are reward-sensitive, like Krylov and BEBFs; they dilate the reward function geometrically through transition matrix. However, when discount factor 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 approaches to 1, Krylov and BEBFs converge slowly. This is because the error Krylov based methods are restricted by Chebyshev polynomial bound.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> To solve this problem, methods such as BARBs are proposed. BARBs is an incremental variant of Drazin bases, and converges faster than Krylov and BEBFs when 
 
 
 
 γ
 
 
 {\displaystyle \gamma }
 
 becomes large.
Another type is reward-insensitive proto value basis function derived from graph Lapalacian. This method uses graph information, but the construction of adjacency matrix makes this method hard to analyze.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dynamic_programming/CLcabtmk">Dynamic programming</a></li>
<li><a href="/facts/Bellman_equation/Qh2gKSMH">Bellman equation</a></li>
<li><a href="/facts/Optimal_control/9SmcQHjJ">Optimal control</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www-all.cs.umass.edu/">[1]</a> UMASS ALL lab</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">[No reference provided in original] <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Keller, Philipp; Mannor, Shie; Precup, Doina. (2006) Automatic Basis Function Construction for Approximate Dynamic Programming and Reinforcement Learning. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA. <a href="/wiki/Doina_Precup" target="_blank">/wiki/Doina_Precup</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction.(1998) MIT Press, Cambridge, MA, chapter 8 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Mahadevan, Sridhar; Maggioni, Mauro. (2005) Value function approximation with diffusion wavelets and Laplacian eigenfuctions. Proceedings of Advances in Neural Information Processing Systems. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Mahadevan, Sridhar; Maggioni, Mauro. (2005) Value function approximation with diffusion wavelets and Laplacian eigenfuctions. Proceedings of Advances in Neural Information Processing Systems. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ilse C. F. Ipsen and Carl D. Meyer. The idea behind Krylov methods. American Mathematical Monthly, 105(10):889–899, 1998. <a href="/wiki/Ilse_Ipsen" target="_blank">/wiki/Ilse_Ipsen</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">M. Petrik. An analysis of Laplacian methods for value function approximation in MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 2574–2579, 2007 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">M. Petrik. An analysis of Laplacian methods for value function approximation in MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 2574–2579, 2007 <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">R. Parr, C. Painter-Wakefield, L.-H. Li, and M. Littman. Analyzing feature generation for value-function approximation. In ICML’07, 2007. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">S. Mahadevan and B. Liu. Basis construction from power series expansions of value functions. In NIPS’10, 2010 <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">William J. Stewart. Numerical methods for computing stationary distributions of finite irreducible Markov chains. In Advances in Computational Probability. Kluwer Academic Publishers, 1997. <a href="/wiki/Markov_chain" target="_blank">/wiki/Markov_chain</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">M. Petrik. An analysis of Laplacian methods for value function approximation in MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 2574–2579, 2007 <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">M. Petrik. An analysis of Laplacian methods for value function approximation in MDPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 2574–2579, 2007 <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

Automatic basis function construction open-in-new

Automatic basis function construction