DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes
This paper presents an algorithm for finding approximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it approximately. It exploits factored representations to achieve compactness and efficiency and to discover connectivity properti...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
AAAI Press/International Joint Conferences on Artificial Intelligence
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90898 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
| _version_ | 1826209886540660736 |
|---|---|
| author | Barry, Jennifer Kaelbling, Leslie P. Lozano-Perez, Tomas |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Barry, Jennifer Kaelbling, Leslie P. Lozano-Perez, Tomas |
| author_sort | Barry, Jennifer |
| collection | MIT |
| description | This paper presents an algorithm for finding approximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it approximately. It exploits factored representations to achieve compactness and efficiency and to discover connectivity properties of the domain. We provide a bound on the quality of the solutions and give asymptotic analysis of the runtimes; in addition we demonstrate performance on a collection of very large domains. Results show that the quality of resulting policies is very good and the total running times, for both creating and solving the hierarchy, are significantly less than for an optimal factored MDP solver. |
| first_indexed | 2024-09-23T14:34:02Z |
| format | Article |
| id | mit-1721.1/90898 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:34:02Z |
| publishDate | 2014 |
| publisher | AAAI Press/International Joint Conferences on Artificial Intelligence |
| record_format | dspace |
| spelling | mit-1721.1/908982022-10-01T21:43:50Z DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes Barry, Jennifer Kaelbling, Leslie P. Lozano-Perez, Tomas Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Barry, Jennifer Kaelbling, Leslie P. Lozano-Perez, Tomas This paper presents an algorithm for finding approximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it approximately. It exploits factored representations to achieve compactness and efficiency and to discover connectivity properties of the domain. We provide a bound on the quality of the solutions and give asymptotic analysis of the runtimes; in addition we demonstrate performance on a collection of very large domains. Results show that the quality of resulting policies is very good and the total running times, for both creating and solving the hierarchy, are significantly less than for an optimal factored MDP solver. United States. Office of Naval Research (ONR MURI grant N00014-09-1-1051) United States. Air Force Office of Scientific Research (AFOSR grant AOARD-104135) 2014-10-10T17:43:26Z 2014-10-10T17:43:26Z 2011-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-57735-512-0 978-1-57735-516-8 http://hdl.handle.net/1721.1/90898 Barry, Jennifer, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. "DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes. In 22nd 2011 International Joint Conference on Artificial Intelligence, IJCAI-11, Barcelona, Catalonia, Spain, 16–22 July 2011. AAAI Press, (2011): p.1928-1935. https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 en_US http://ijcai.org/papers11/Papers/IJCAI11-323.pdf Proceedings of the 22nd 2011 International Joint Conference on Artificial Intelligence Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf AAAI Press/International Joint Conferences on Artificial Intelligence MIT web domain |
| spellingShingle | Barry, Jennifer Kaelbling, Leslie P. Lozano-Perez, Tomas DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title | DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title_full | DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title_fullStr | DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title_full_unstemmed | DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title_short | DetH*: Approximate Hierarchical Solution of Large Markov Decision Processes |
| title_sort | deth approximate hierarchical solution of large markov decision processes |
| url | http://hdl.handle.net/1721.1/90898 https://orcid.org/0000-0002-8657-2450 https://orcid.org/0000-0001-6054-7145 |
| work_keys_str_mv | AT barryjennifer dethapproximatehierarchicalsolutionoflargemarkovdecisionprocesses AT kaelblinglesliep dethapproximatehierarchicalsolutionoflargemarkovdecisionprocesses AT lozanopereztomas dethapproximatehierarchicalsolutionoflargemarkovdecisionprocesses |