mlsanityData to 14 Oct 2026

Finding Options that Minimize Planning Time

arXiv 1810.07311 ↗First posted 16 Oct 2018cs.AIcited by 17

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 5; 2024: 3; 2025: 1; 2026: 3.

17 papers.

Sort:

By area:

  1. 2021Temporal Abstraction in Reinforcement Learning with the Successor Representationcited by 54
  2. 2023Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Provingcited by 37
  3. 2022Humans decompose tasks by trading off utility and computational costcited by 18
  4. 2023Scalable Multi-agent Covering Option Discovery based on Kronecker Graphscited by 9
  5. 2026Compositional Planning with Jumpy World Modelscited by 7
  6. 2026Laplacian Representations for Decision-Time Planningcited by 5
  7. 2022Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphscited by 4
  8. 2026Intelligence as Managed Autonomy: Failure, Escalation, and Governance for Agentic AI Systemscited by 4
  9. 2022Toward Discovering Options that Achieve Faster Planningcited by 3
  10. 2025OptionZero: Planning with Learned Optionscited by 2
  11. 2023Offline Skill Graph (OSG): A Framework for Learning and Planning using Offline Reinforcement Learning Skillscited by 1
  12. 2023Iterative Option Discovery for Planning, by Planningcited by 1
5 more
  1. 2023SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solvingcited by 1
  2. 2024MENTOR: Guiding Hierarchical Reinforcement Learning with Human Feedback and Dynamic Distance Constraintcited by 1
  3. 2024Subgoal Discovery Using a Free Energy Paradigm and State Aggregationscited by 1
  4. 2022Multi-Task Option Learning and Discovery for Stochastic Path Planningcited by 0
  5. 2024A New View on Planning in Online Reinforcement Learningcited by 0