Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery
Solving large scale sequential decision making problems without prior knowledge of the state transition model is a key problem in the planning literature. One approach to tackle this problem is to learn the state transition model online using limited observed measurements. We present an adaptive fun...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81767 https://orcid.org/0000-0002-2508-1957 https://orcid.org/0000-0001-8576-1930 |
| _version_ | 1826199867584675840 |
|---|---|
| author | Geramifard, Alborz Chowdhary, Girish How, Jonathan P. Ure, Nazim Kemal |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Geramifard, Alborz Chowdhary, Girish How, Jonathan P. Ure, Nazim Kemal |
| author_sort | Geramifard, Alborz |
| collection | MIT |
| description | Solving large scale sequential decision making problems without prior knowledge of the state transition model is a key problem in the planning literature. One approach to tackle this problem is to learn the state transition model online using limited observed measurements. We present an adaptive function approximator (incremental Feature Dependency Discovery (iFDD)) that grows the set of features online to approximately represent the transition model. The approach leverages existing feature-dependencies to build a sparse representation of the state transition model. Theoretical analysis and numerical simulations in domains with state space sizes varying from thousands to millions are used to illustrate the benefit of using iFDD for incrementally building transition models in a planning framework. |
| first_indexed | 2024-09-23T11:27:04Z |
| format | Article |
| id | mit-1721.1/81767 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:27:04Z |
| publishDate | 2013 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/817672022-10-01T03:42:51Z Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery Geramifard, Alborz Chowdhary, Girish How, Jonathan P. Ure, Nazim Kemal Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Ure, Nazim Kemal Geramifard, Alborz Chowdhary, Girish How, Jonathan P. Solving large scale sequential decision making problems without prior knowledge of the state transition model is a key problem in the planning literature. One approach to tackle this problem is to learn the state transition model online using limited observed measurements. We present an adaptive function approximator (incremental Feature Dependency Discovery (iFDD)) that grows the set of features online to approximately represent the transition model. The approach leverages existing feature-dependencies to build a sparse representation of the state transition model. Theoretical analysis and numerical simulations in domains with state space sizes varying from thousands to millions are used to illustrate the benefit of using iFDD for incrementally building transition models in a planning framework. 2013-10-25T13:18:47Z 2013-10-25T13:18:47Z 2012-09 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-33485-6 978-3-642-33486-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/81767 Ure, N.Kemal et al. “Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery.” Machine Learning and Knowledge Discovery in Databases. Ed. PeterA. Flach, Tijl Bie, and Nello Cristianini. Vol. 7524. Springer Berlin Heidelberg, 2012. 99–115. Lecture Notes in Computer Science. https://orcid.org/0000-0002-2508-1957 https://orcid.org/0000-0001-8576-1930 en_US http://dx.doi.org/10.1007/978-3-642-33486-3_7 Machine Learning and Knowledge Discovery in Databases Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag Other University Web Domain |
| spellingShingle | Geramifard, Alborz Chowdhary, Girish How, Jonathan P. Ure, Nazim Kemal Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title | Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title_full | Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title_fullStr | Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title_full_unstemmed | Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title_short | Adaptive Planning for Markov Decision Processes with Uncertain Transition Models via Incremental Feature Dependency Discovery |
| title_sort | adaptive planning for markov decision processes with uncertain transition models via incremental feature dependency discovery |
| url | http://hdl.handle.net/1721.1/81767 https://orcid.org/0000-0002-2508-1957 https://orcid.org/0000-0001-8576-1930 |
| work_keys_str_mv | AT geramifardalborz adaptiveplanningformarkovdecisionprocesseswithuncertaintransitionmodelsviaincrementalfeaturedependencydiscovery AT chowdharygirish adaptiveplanningformarkovdecisionprocesseswithuncertaintransitionmodelsviaincrementalfeaturedependencydiscovery AT howjonathanp adaptiveplanningformarkovdecisionprocesseswithuncertaintransitionmodelsviaincrementalfeaturedependencydiscovery AT urenazimkemal adaptiveplanningformarkovdecisionprocesseswithuncertaintransitionmodelsviaincrementalfeaturedependencydiscovery |