ICML 2019oral50 citations
Finding Options that Minimize Planning Time
Yuu Jinnai, David Abel, David Hershkowitz, Michael Littman, George Konidaris
Abstract
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.
BibTeX
@InProceedings{pmlr-v97-jinnai19a,
title = {Finding Options that Minimize Planning Time},
author = {Jinnai, Yuu and Abel, David and Hershkowitz, David and Littman, Michael and Konidaris, George},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {3120--3129},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/jinnai19a/jinnai19a.pdf},
url = {https://proceedings.mlr.press/v97/jinnai19a.html},
abstract = {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.}
}