Proceedings

Markovian State and Action Abstractions for MDPs via Hierarchical MCTS

Aijun Bai, Siddharth Srivastava, Stuart J. Russell

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3029-3038.

Abstract

State abstraction is an important technique for scaling MD Palgorithms. As is well known, however, it introduces difficulties due to the non-Markovian nature of state-abstracted models. Whereas prior approaches rely upon ad hoc fixes for this issue, we propose instead to view the state-abstracted model as a POMDP and show that we can thereby take advantage of state abstraction without sacrificing the Markov property. We further exploit the hierarchical structure introduced by state abstraction by extending the theory of options to a POMDP setting. In this context we propose a hierarchical Monte Carlo tree search algorithm and show that it converges to a recursively optimal hierarchical policy. Both theoretical and empirical results suggest that abstracting an MDP into a POMDP yields a scalable solution approach.

Aijun Bai, Siddharth Srivastava, and Stuart J. Russell. 2016. Markovian State and Action Abstractions for MDPs via Hierarchical MCTS. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3029–3038. https://ijcai.org/proceedings/2016/430
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards