Compositional Planning Using Optimal Option Models. Silver Ciosek. ICML 2012


Videolecture at http://techtalks.tv/talks/compositional-planning-using-optimal-option-models/57443/

  1. Options are closed-loop subpolicies that have some terminating condition
  2. An option-model describes the distribution of states upon termination of the option
  3. Distinguishes between
    1. intra-option model learning: constructing option models from primitive actions
    2. inter-option planning: using option models to construct a value function
  4. Option models can be composed to create more abstract option models
  5. In most work, the assumption is that options are created, then a value function is computed, this paper seems to interleave the process at multiple levels of hierarchy
  6. Sutton’s earlier work somewhat dealt with this, but it was in the off-policy, or Markov chain setting
  7. Precup’s work provided a method to compute the value function (and therefore policies) from option models, but not into other options
  8. In general, the options framework is agnostic to how options are created, but some algorithms that tackle option creation explicitly are MAXQ and HAM
    1. These algorithms, though, are designed for the “full” learning setting and not planning (which I suppose is what is being considered here).
    2. May be relying on full knowledge of dynamics instead of generative model.
  9. They work with Tower of Hanoi and a hierarchical path planning problem and say traditional methods have costs exponential in the size of the problem, but it’s polynomial, so my assumption is they mean it is exponential in a compact (as opposed to flat) representation
    1. Cite a paper that conducts “macro actions” that makes it poly time.  Need to read.
  10. Looks like they are working in a setting that has reward distributions and impure policies
  11. Interestingly, the transition matrix as defined for options is discounted in the length of time the option takes before reaching the terminating condition.  This is based on the interpretation that each step in between there is a 1-γ probability of termination.  I’m sure its needed to make the math go through
  12. The math itself is fairly dense linear algebra – don’t have time to grok deeply at the moment
    1. Some statements not quite following at the moment? 
    2. True value Model G-  is a lower bound on all policies from all states.  I’m sure I would find out why this is useful.  They say it basically says that policy models dominate option models.
      1. I suppose a policy model is the (discounted?) distribution over states from a given start state?
      2. Its not clear to me how a model can dominate another model – they are both just estimates of distributions over states.  These distributions have different values, so I suppose its a bit of an abuse of language?
      3. Oh I see, they define value models and say that policy models are value models
  13. A bit tough to read on first pass because a lot of standard RL stuff is defined a bit differently
  14. They rewrite the Bellman equation in terms of the math they defined and work from that
  15. Their generalization of VI, OOMI does not impose any option hierarchy; all option models may be composed of any other option model
  16. Say that even if OOMI is presented only with primitive actions it may converge in “significantly fewer iterations than VI”
  17. Has an order of magnitude savings over two other planning methods (much more sophisticated than VI) Action-policy model iteration, and Action-option-policy model iteration
    1. In deterministic Tower of Hanoi, the number of iterations is essentially just the number of disks, whereas other algs are exponential in the number of disks
  18. “This is the first MDP planning algorithm to dynamically create its own planning operators.  These operators are composed together to give increasingly deep and purposeful jumps through state space.”

Talk

  1. Talk gives the analogy of starting with bricks, composing brick laying to make a wall, and then composing walls to make buildings
  2. The composition of option models is just matrix multiplication
  3. Optimal option models (optimal at reaching some subgoal) make good macro-operators.
  4. Ah this notation is from Sutton
  5. Talk is a good quick overview of the paper
  6. One equation is pretty similar to the standard Bellman equation, in linear algebra form, then with an application of options, but then the equation is expressed in a different form
  7. This equation defines models that plan wrt to subgoal model.  This is the Bellman equation that defines the optimality of an option wrt to provided termination condition, G.
    1. Calls this the optimal option
  8. The natural question then is where do the Gs come from?
  9. When planning, use provided options while composing new options from those that exist
  10. Seems like the initial set of subgoals and models are provided a-priori, but perhaps they can just be built up from primitives?
  11. Like VI, its an iterative procedure
    1. Each iteration updates all option models
    2. This is beneficial because as iterations improve, ability to solve all subgoals improves, and all options can simultaneously take advantage of those improvements
  12. These model equations are contraction operators, so thats good
  13. Looks like the empirical results have manually defined subgoals, which does simlify the planning problem and requires domain expertise
  14. Of emprical competitors, one is a flat planner similar to VI, another composes options during an initial period and then plans with those options, and this algorithms interleaves progress

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: