Toward Discovering Options that Achieve Faster Planning
  We propose a new objective for option discovery that emphasizes the
computational advantage of using options in planning. For a given set of
episodic tasks and a given number of options, the objective prefers options
that can be used to achieve a high return by composing few options. By
composing few options, fast planning can be achieved. When faced with new tasks
similar to the given ones, the discovered options are also expected to
accelerate planning. Our objective extends the objective proposed by Harb et
al. (2018) for the single-task setting to the multi-task setting. A closer look
at Harb et al.'s objective shows that the best options discovered given one
task are not likely to be useful for future unseen tasks and that the
multi-task setting is indeed necessary for this purpose. In the same paper,
Harb et al. also proposed an algorithm to optimize their objective, and the
algorithm can be naturally extended to the multi-task setting. We empirically
show that in the four-room domain the extension does not achieve a high
objective value and propose a new algorithm that better optimizes the proposed
objective. In the same four-room domain, we show that 1) a higher objective
value is typically associated with options with which fewer planning iterations
are needed to achieve near-optimal performance, 2) our new algorithm achieves a
high objective value, which is close to the value achieved by a set of
human-designed options, 3) the best number of planning iterations given the
discovered options is much smaller and matches it obtained given human-designed
options, and 4) the options produced by our algorithm also make intuitive sense
because they move to and terminate at cells near hallways connecting two
neighbor rooms.
