# Toward Discovering Options that Achieve Faster Planning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 12 of 12)

- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Data-Efficient Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1805.08296/) (2018)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Eigenoption Discovery through the Deep Successor Representation](https://mlsanity.com/paper/1710.11089/) (2017)
- [When Waiting is not an Option : Learning Options with a Deliberation Cost](https://mlsanity.com/paper/1709.04571/) (2017)
- [Discovering Options for Exploration by Minimizing Cover Time](https://mlsanity.com/paper/1903.00606/) (2019)
- [Options of Interest: Temporal Abstraction with Interest Functions](https://mlsanity.com/paper/2001.00271/) (2020)
- [Discovery of Options via Meta-Learned Subgoals](https://mlsanity.com/paper/2102.06741/) (2021)
- [The Termination Critic](https://mlsanity.com/paper/1902.09996/) (2019)
- [Finding Options that Minimize Planning Time](https://mlsanity.com/paper/1810.07311/) (2018)

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

- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Iterative Option Discovery for Planning, by Planning](https://mlsanity.com/paper/2310.01569/) (2023)
- [Subgoal Discovery Using a Free Energy Paradigm and State Aggregations](https://mlsanity.com/paper/2412.16687/) (2024)

## Abstract (arXiv)

We propose a new objective for option discovery that emphasizes the computational advantage of using options in planning. In a sequential machine, the speed of planning is proportional to the number of elementary operations used to achieve a good policy. For episodic tasks, the number of elementary operations depends on the number of options composed by the policy in an episode and the number of options being considered at each decision point. To reduce the amount of computation in planning, for a given set of episodic tasks and a given number of options, our objective prefers options with which it is possible to achieve a high return by composing few options, and also prefers a smaller set of options to choose from at each decision point. We develop an algorithm that optimizes the proposed objective. In a variant of the classic four-room domain, we show that 1) a higher objective value is typically associated with fewer number of elementary planning operations used by the option-value iteration algorithm to obtain a near-optimal value function, 2) our algorithm achieves an objective value that matches it achieved by two human-designed options 3) the amount of computation used by option-value iteration with options discovered by our algorithm matches it with the human-designed options, 4) the options produced by our algorithm also make intuitive sense--they seem to move to and terminate at the entrances of rooms.