Constructing skill trees

CST (Constructing skill trees) is a hierarchical reinforcement learning algorithm which can build skill trees from a set of sample solution trajectories obtained from demonstration. CST uses an incremental MAP(maximum a posteriori ) change point detection algorithm to segment each demonstration trajectory into skills and integrate the results into a skill tree. CST was introduced by George Konidaris, Scott Kuindersma, Andrew Barto and Roderic Grupen in 2010.

Algorithm

CST consists of mainly three parts;change point detection, alignment and merging. The main focus of CST is online change-point detection. The change-point detection algorithm is used to segment data into skills and uses the sum of discounted reward $R_{t}^{}$ as the target regression variable. Each skill is assigned an appropriate abstraction. A particle filter is used to control the computational complexity of CST.

The change point detection algorithm is implemented as follows. The data for times $t\in T$ and models Q with prior $p(q\in Q)$ are given. The algorithm is assumed to be able to fit a segment from time $j+1$ to $t$ using model $q$ with the fit probability $P(j,t,q)_{}^{}$ . A linear regression model with Gaussian noise is used to compute $P(j,t,q)_{}^{}$ . The Gaussian noise prior has mean zero, and variance which follows $InverseGamma({\frac {v}{2}},{\frac {u}{2}})$ . The prior for each weight follows $Normal_{}^{}(0,\sigma ^{2}\delta )$ . The fit probability $P(j,t,q)_{}^{}$ is computed by the following equation.

$P(j,t,q)={\frac {\pi ^{-{\frac {n}{2}}}}{\delta ^{m}}}\left|(A+D)^{-1}\right|^{\frac {1}{2}}{\frac {u^{\frac {v}{2}}}{(y+u)^{\frac {u+v}{2}}}}{\frac {\Gamma ({\frac {n+v}{2}})}{\Gamma ({\frac {v}{2}})}}$

Then, CST compute the probability of the changepoint at time j with model q, $P_{t}^{}(j,q)$ and $P_{j}^{MAP}$ using an Viterbi algorithm.

$P_{t}(j,q)=(1-G(t-j-1))P(j,t,q)p(q)P_{j}^{MAP}$

$P_{j}^{MAP}=\max _{i,q}{\frac {P_{j}(i,q)g(j-i)}{1-G(j-i-1)}},\forall j<t$

The description of the parameters and variables are as follows;

$A=\sum _{t=j}^{t}\Phi (x_{i})\Phi (x_{i})^{T}$

$\Phi (x_{i})_{}^{}$ : a vector of m basis functions evaluated at state $x_{i}$

$y=(\sum _{i=j}^{t}R_{i}^{2})-b^{T}(A+D)^{-1}b$

$b=\sum _{i=j}^{t}R_{i}\Phi (x_{i})$

$R_{i}=\sum _{j=i}^{T}\gamma ^{j-i}r_{j}$

$\Gamma _{}^{}$ : Gamma function

$n_{}^{}=t-j$

$m_{}^{}$ : The number of basis functions q has.

$D_{}^{}$ : an m by m matrix with $\delta ^{-1}$ on the diagonal and zeros else where

The skill length $l$ is assumed to follow a Geometric distribution with parameter p

$g_{}^{}(l)=(1-p)^{l-1}p$

$G_{}^{}(l)=(1-(1-p)^{l})$

$p_{}^{}={\frac {1}{k}}$

$k_{}^{}:$ Expected skill length

Using the method above, CST can segment data into a skill chain. The time complexity of the change point detection is $O(NL)$ and storage size is $O(Nc)$ , where $N$ is the number of particles, $L$ is the time of computing $P(j,t,q)$ , and there are $O(c)$ change points.

Next step is alignment. CST needs to align the component skills because the change-point does not occur in the exactly same places. Thus, when segmenting two trajectories sequentially, it includes a bias on change point location in the second trajectory. This bias follows a mixture of gaussians.

The last step is merging. CST merges skill chains into a skill tree. CST merges a pair of trajectory segments by allocating the same skill. All trajectories have the same goal and it merges two chains by starting at their final segments. If two segments are statistically similar, it merges them. This procedure is repeated until it fails to merge a pair of skill segments. $P(j,t,q)$ are used to determine whether a pair of trajectories are modeled better as one skill or as two different skills.

Pseudocode

The following pseudocode describes the chagepoint detection algorithm:

  particles = [];
  Process each incoming data point
  for t=1:T
     //Compute fit probabilities for all particles      
     for  $p\in particles$  
        p_tjq=(1-G(t-p.pos-1))*p.fit_prob*model_prior(p.model)*p.prev_MAP 
        p.MAP=p_tjq*g(t-p.pos)/(1-G(t-p.pos-1))
     end
     //Filter if necessary
     if the number of particles >= N
        particles=particle_filter(p.MAP, M)
     end
     //Determine the Viterbi path
     for t==1
        max_path=[]
        max_MAP=1/|Q|
     else
        max_particle= $\max _{p}$ p.MAP
        max_path=max_particle.path  $\cup$  max_particle
        max_MAP=max_particle.MAP
     end
     //Create new particles for a changepoint at time t
     for  $q\in Q$ 
        new_p=create_particle(model=q, pos=t, prev_MAP=max_MAP, path=max_path)
        p=p  $\cup$  new_p
     end
     //Update all particles
     for  $p\in P$ 
        particles=update_particle(current_state, current_reward,p)      
     end
  end
  //Return the most likely path to the final point
  return max_path

  function update_particle(current_state, current_reward, particle);
  p=particle
  r_t=current_reward
  //Initialization
  if t==0
     p.A=zero matrix(p.m,p.m)
     p.b=zero vector(p.m)
     p.z=zero vector(p.m)
     p.sum r=0
     p.tr1=0
     p.tr2=0
  end
  //Compute the basis function vector for the current state
   $\Phi _{t}$ =p. $\Phi$ (current state)
  //Update sufficient statistics
  p.A=p.A+ $\Phi _{t}\Phi _{t}^{T}$ 
  p.z= $\gamma$ p.z+ $\Phi _{t}$ 
  p.b=p.b+ $r_{t}$  p.z
  p.tr1=1+  $\gamma ^{2}$  p.tr1
  p.sum r=sum p.r+  $r_{t}^{2}$  p.tr1+2 $\gamma r_{t}$  p.tr2
  p.tr2= $\gamma$ p.tr2+ $r_{t}$  p.tr1
  p.fit_prob=compute_fit_prob(p,v,u,delta, $\gamma$ )

Uses

CST has been used to acquire skills from human demonstration in the PinBall domain. It has been also used to acquire skills from human demonstration on a mobile manipulator.

Assumptions

CTS assume that the demonstrated skills form a tree, the domain reward funcition is known and the best model for merging a pair of skills is the model selected for representing both individually.

Advantages

CTS is a faster algorithm than skill chaining. Skill can be learned and represented efficiently since they allocated their own abstraction. This allows to learn higher dimensional policies. Even unsuccessful episode can improve skills. Skills acquired using agent-centric features can be used for other problems.

References

Konidaris, George (2010). "Constructing Skill Trees for Reinforcement Learning Agents from Demonstration Trajectories". Advances in Neural Information Processing Systems 23. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

Konidaris, George (2009). "Skill discovery in continuous reinforcement learning domains using skill chaining". Advances in Neural Information Processing Systems 22. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

Fearnhead, Paul (2007). "On-line Inference for Multiple Change Points". Journal of the Royal Statistical Society. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)