# Finding Options that Minimize Planning Time

arXiv: https://arxiv.org/abs/1810.07311 · HTML: https://mlsanity.com/paper/1810.07311/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2018.

## Built on by (most cited first, 17 of 17)

- [Temporal Abstraction in Reinforcement Learning with the Successor Representation](https://mlsanity.com/paper/2110.05740/) (2021)
- [Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Proving](https://mlsanity.com/paper/2305.16366/) (2023)
- [Humans decompose tasks by trading off utility and computational cost](https://mlsanity.com/paper/2211.03890/) (2022)
- [Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs](https://mlsanity.com/paper/2307.11629/) (2023)
- [Compositional Planning with Jumpy World Models](https://mlsanity.com/paper/2602.19634/) (2026)
- [Laplacian Representations for Decision-Time Planning](https://mlsanity.com/paper/2602.05031/) (2026)
- [Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs](https://mlsanity.com/paper/2201.08227/) (2022)
- [Intelligence as Managed Autonomy: Failure, Escalation, and Governance for Agentic AI Systems](https://mlsanity.com/paper/2605.27628/) (2026)
- [Toward Discovering Options that Achieve Faster Planning](https://mlsanity.com/paper/2205.12515/) (2022)
- [OptionZero: Planning with Learned Options](https://mlsanity.com/paper/2502.16634/) (2025)
- [Offline Skill Graph (OSG): A Framework for Learning and Planning using Offline Reinforcement Learning Skills](https://mlsanity.com/paper/2306.13630/) (2023)
- [Iterative Option Discovery for Planning, by Planning](https://mlsanity.com/paper/2310.01569/) (2023)
- [SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving](https://mlsanity.com/paper/2310.12960/) (2023)
- [MENTOR: Guiding Hierarchical Reinforcement Learning with Human Feedback and Dynamic Distance Constraint](https://mlsanity.com/paper/2402.14244/) (2024)
- [Subgoal Discovery Using a Free Energy Paradigm and State Aggregations](https://mlsanity.com/paper/2412.16687/) (2024)
- [Multi-Task Option Learning and Discovery for Stochastic Path Planning](https://mlsanity.com/paper/2210.00068/) (2022)
- [A New View on Planning in Online Reinforcement Learning](https://mlsanity.com/paper/2406.01562/) (2024)

## Abstract (arXiv)

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.