Finding Options that Minimize Planning Time

Yuu Jinnai, David Abel, David Hershkowitz, Michael Littman, George Konidaris
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3120-3129, 2019.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T Finding Options that Minimize Planning Time %A Yuu Jinnai %A David Abel %A David Hershkowitz %A Michael Littman %A George Konidaris %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-jinnai19a %I PMLR %P 3120--3129 %U https://proceedings.mlr.press/v97/jinnai19a.html %V 97 %X 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.
APA
Jinnai, Y., Abel, D., Hershkowitz, D., Littman, M. & Konidaris, G.. (2019). Finding Options that Minimize Planning Time. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3120-3129 Available from https://proceedings.mlr.press/v97/jinnai19a.html.

Related Material