Finding Options that Minimize Planning Time
  We formalize the problem of selecting the optimal set of options for planning
as that of computing the smallest set of options so that planning converges in
less than a given maximum of value-iteration passes. We first show that the
problem is NP-hard, even if the task is constrained to be deterministic---the
first such complexity result for option discovery. We then present the first
polynomial-time boundedly suboptimal approximation algorithm for this setting,
and empirically evaluate it against both the optimal options and a
representative collection of heuristic approaches in simple grid-based domains
including the classic four-rooms problem.
