Skill Characterization Based on Betweenness. Simsek, Barto. NIPS 2008.
“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.”
Does not require “…representing the interaction graph in its entirety.”
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
Define subgoals as states that have higher betweeness than adjacent states
Use tic-tac-toe, taxi, and playroom as examples
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.
Playroom bottlenecks are probably a bit more diverse/complex as they aren’t listed explicitly
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)
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
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