Automated State Abstraction for Options using the U-Tree Algorithm. Jonsson, Barto. NIPS 2001


  1. Adapts McCallum’s U-tree algorithm to automatically build option-specific representations of the state feature space
  2. When using with options, can deal with features only relevant to current subtask
  3. This feature selection causes policies to be more compact and can increase generalization
  4. Dietterich’s MAXQ requires the relevant set of each “action” (option?) prior to learning
    1. This becomes difficult to do by hand as problem complexity grows; we may not know how to do it ourselves
  5. U-tree algorithm doesn’t require such things to be specified by hand
  6. U-Tree keeps track of SARSes
  7. The tree is a form of decision tree, each leaf has a Q-estimate
  8. Also does standard model building – T and R, which is used for sweeps of VI
  9. Tests to determine leaf splitting are a little more complex, but only get surface treatment so far so I’m not sure what they are in particular.  Seem to have a temporal component and add whole subtrees, not just a simple split?
  10. Separate tree for each action
  11. Likewise can just build trees for each option
  12. And can be extended for intra-option learning
  13. Oh looks like in the general treatment U-trees can work on a history (higher order Markov).  They test in taxi which is Markovian so they dont maintain extended histories
  14. I suppose because its a NIPS paper and space is limited, things aren’t really able to be treated as thoroughly as they need to be.
  15. Oh I see, they say that automated state abstraction for options are achieved because the decision tree only splits on features that matter.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: