Skill Characterization Based on Betweenness. Simsek, Barto. NIPS 2008.


  1. “We present a characterization of a useful class of skills based on a graphical representation of an agent’s interaction with its environment.  Our characterization uses betweeness, a measure of centrality [bottleneck] on graphs.”
  2. Does not require “…representing the interaction graph in its entirety.”
  3. Propose a measure in navigation tasks which is how what ratio of shortest-length paths go through each node.  When path weights are uniform this is equal to betweeness – takes O(nm) time for n nodes and m edges.  On weighted graphs this becomes  O(nm+n^2 logn) – still not considering stochasticity in this cost I believe
  4. Define subgoals as states that have higher betweeness than adjacent states
  5. Use tic-tac-toe, taxi, and playroom as examples
    1. Taxi: “highest local maxima of betweeness correspond to passenger delivery”.  Others are being at passenger location, at a passenger location with passenger in car, taxi and passenger at destination point, or when the taxi is at one of 2 navigational bottlenecks.
    2. Playroom bottlenecks are probably a bit more diverse/complex as they aren’t listed explicitly
    3. In tic-tac-toe, the bottlenecks are states that allow a win in three plies regardless of opponent response (which aren’t reachable if both players are playing correctly)
  6. Random skills (I guess these are just randomly placed subgoals) improved performance over working only with primitive actions, but having skills computed their way was best
  7. Because their metric for betweeness is local (just immediate neighbors), it doesn’t require the full graph to be represented in order to calculate it 
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: